O(1)-Approximations for Maximum Movement Problems View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2011

AUTHORS

Piotr Berman , Erik D. Demaine , Morteza Zadimoghaddam

ABSTRACT

We develop constant-factor approximation algorithms for minimizing the maximum movement made by pebbles on a graph to reach a configuration in which the pebbles form a connected subgraph (connectivity), or interconnect a constant number of stationary nodes (Steiner tree). These problems model the minimization of the total time required to reconfigure a robot swarm to achieve a proximity (e.g., radio) network with these connectivity properties. Our approximation factors are tight up to constant factors, as none of these problems admit a (2 − ε)-approximation assuming P ≠ NP. More... »

PAGES

62-74

Book

TITLE

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

ISBN

978-3-642-22934-3
978-3-642-22935-0

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-22935-0_6

DOI

http://dx.doi.org/10.1007/978-3-642-22935-0_6

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1045076916


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0102", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Applied Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Engineering, Pennsylvania State University, 16802, University Park, PA, USA", 
          "id": "http://www.grid.ac/institutes/grid.29857.31", 
          "name": [
            "Department of Computer Science and Engineering, Pennsylvania State University, 16802, University Park, PA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Berman", 
        "givenName": "Piotr", 
        "id": "sg:person.01274506210.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "MIT Computer Science and Artificial Intelligence Laboratory, 32 Vassar St., 02139, Cambridge, MA, USA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "MIT Computer Science and Artificial Intelligence Laboratory, 32 Vassar St., 02139, Cambridge, MA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Demaine", 
        "givenName": "Erik D.", 
        "id": "sg:person.015206033153.81", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015206033153.81"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "MIT Computer Science and Artificial Intelligence Laboratory, 32 Vassar St., 02139, Cambridge, MA, USA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "MIT Computer Science and Artificial Intelligence Laboratory, 32 Vassar St., 02139, Cambridge, MA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Zadimoghaddam", 
        "givenName": "Morteza", 
        "id": "sg:person.07611416301.10", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07611416301.10"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2011", 
    "datePublishedReg": "2011-01-01", 
    "description": "We develop constant-factor approximation algorithms for minimizing the maximum movement made by pebbles on a graph to reach a configuration in which the pebbles form a connected subgraph (connectivity), or interconnect a constant number of stationary nodes (Steiner tree). These problems model the minimization of the total time required to reconfigure a robot swarm to achieve a proximity (e.g., radio) network with these connectivity properties. Our approximation factors are tight up to constant factors, as none of these problems admit a (2\u2009\u2212\u2009\u03b5)-approximation assuming P\u2009\u2260\u2009NP.", 
    "editor": [
      {
        "familyName": "Goldberg", 
        "givenName": "Leslie Ann", 
        "type": "Person"
      }, 
      {
        "familyName": "Jansen", 
        "givenName": "Klaus", 
        "type": "Person"
      }, 
      {
        "familyName": "Ravi", 
        "givenName": "R.", 
        "type": "Person"
      }, 
      {
        "familyName": "Rolim", 
        "givenName": "Jos\u00e9 D. P.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-22935-0_6", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-22934-3", 
        "978-3-642-22935-0"
      ], 
      "name": "Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques", 
      "type": "Book"
    }, 
    "keywords": [
      "constant-factor approximation algorithm", 
      "connectivity properties", 
      "approximation algorithm", 
      "approximation factor", 
      "constant factor", 
      "approximation", 
      "connected subgraph", 
      "proximity networks", 
      "constant number", 
      "movement problems", 
      "problem", 
      "stationary nodes", 
      "maximum movement", 
      "robot swarms", 
      "graph", 
      "subgraphs", 
      "minimization", 
      "algorithm", 
      "swarm", 
      "NPs", 
      "network", 
      "properties", 
      "configuration", 
      "nodes", 
      "number", 
      "total time", 
      "pebbles", 
      "time", 
      "movement", 
      "factors"
    ], 
    "name": "O(1)-Approximations for Maximum Movement Problems", 
    "pagination": "62-74", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1045076916"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-22935-0_6"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-22935-0_6", 
      "https://app.dimensions.ai/details/publication/pub.1045076916"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-08-04T17:17", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220804/entities/gbq_results/chapter/chapter_270.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-22935-0_6"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-22935-0_6'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-22935-0_6'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-22935-0_6'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-22935-0_6'


 

This table displays all metadata directly associated to this object as RDF triples.

121 TRIPLES      22 PREDICATES      55 URIs      48 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-22935-0_6 schema:about anzsrc-for:01
2 anzsrc-for:0102
3 schema:author N28c985b08e9145ffb0b8ab8d6a0ffc3a
4 schema:datePublished 2011
5 schema:datePublishedReg 2011-01-01
6 schema:description We develop constant-factor approximation algorithms for minimizing the maximum movement made by pebbles on a graph to reach a configuration in which the pebbles form a connected subgraph (connectivity), or interconnect a constant number of stationary nodes (Steiner tree). These problems model the minimization of the total time required to reconfigure a robot swarm to achieve a proximity (e.g., radio) network with these connectivity properties. Our approximation factors are tight up to constant factors, as none of these problems admit a (2 − ε)-approximation assuming P ≠ NP.
7 schema:editor Nec779233d3c949ef80ff0d595742f19e
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf N30f0b3c83dbe406da4a8352430148404
11 schema:keywords NPs
12 algorithm
13 approximation
14 approximation algorithm
15 approximation factor
16 configuration
17 connected subgraph
18 connectivity properties
19 constant factor
20 constant number
21 constant-factor approximation algorithm
22 factors
23 graph
24 maximum movement
25 minimization
26 movement
27 movement problems
28 network
29 nodes
30 number
31 pebbles
32 problem
33 properties
34 proximity networks
35 robot swarms
36 stationary nodes
37 subgraphs
38 swarm
39 time
40 total time
41 schema:name O(1)-Approximations for Maximum Movement Problems
42 schema:pagination 62-74
43 schema:productId N7514da85ded144f2bd931b38b99cb577
44 Na197d23f67014c5da9409704014d4e3d
45 schema:publisher N9dcacaa31b3a4b3f85a59f1ccefb28cc
46 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045076916
47 https://doi.org/10.1007/978-3-642-22935-0_6
48 schema:sdDatePublished 2022-08-04T17:17
49 schema:sdLicense https://scigraph.springernature.com/explorer/license/
50 schema:sdPublisher N7562f0974372476ea7237d94625dadc8
51 schema:url https://doi.org/10.1007/978-3-642-22935-0_6
52 sgo:license sg:explorer/license/
53 sgo:sdDataset chapters
54 rdf:type schema:Chapter
55 N0f55e43f8f154266b7c255d73a5f60ff rdf:first N332e695b883549c5b70cc5a057a43b67
56 rdf:rest rdf:nil
57 N2088e3bde6534422abd7a01bf125b09e schema:familyName Goldberg
58 schema:givenName Leslie Ann
59 rdf:type schema:Person
60 N28c985b08e9145ffb0b8ab8d6a0ffc3a rdf:first sg:person.01274506210.27
61 rdf:rest Nd39c50cccb4d46ad9056c0142f242ac4
62 N30f0b3c83dbe406da4a8352430148404 schema:isbn 978-3-642-22934-3
63 978-3-642-22935-0
64 schema:name Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
65 rdf:type schema:Book
66 N332e695b883549c5b70cc5a057a43b67 schema:familyName Rolim
67 schema:givenName José D. P.
68 rdf:type schema:Person
69 N33ae81e9ab7c4282bd050d1a3067e0a7 rdf:first Nf7214d60e6c44a0ba7caf669188414c7
70 rdf:rest N691051385a5d484f97dcce4584f5e4e1
71 N6875696d54c24e4aa9616365dbac3847 schema:familyName Ravi
72 schema:givenName R.
73 rdf:type schema:Person
74 N691051385a5d484f97dcce4584f5e4e1 rdf:first N6875696d54c24e4aa9616365dbac3847
75 rdf:rest N0f55e43f8f154266b7c255d73a5f60ff
76 N7514da85ded144f2bd931b38b99cb577 schema:name dimensions_id
77 schema:value pub.1045076916
78 rdf:type schema:PropertyValue
79 N7562f0974372476ea7237d94625dadc8 schema:name Springer Nature - SN SciGraph project
80 rdf:type schema:Organization
81 N9dcacaa31b3a4b3f85a59f1ccefb28cc schema:name Springer Nature
82 rdf:type schema:Organisation
83 Na197d23f67014c5da9409704014d4e3d schema:name doi
84 schema:value 10.1007/978-3-642-22935-0_6
85 rdf:type schema:PropertyValue
86 Nd39c50cccb4d46ad9056c0142f242ac4 rdf:first sg:person.015206033153.81
87 rdf:rest Nea0312bfce84433a8e386ada167a3731
88 Nea0312bfce84433a8e386ada167a3731 rdf:first sg:person.07611416301.10
89 rdf:rest rdf:nil
90 Nec779233d3c949ef80ff0d595742f19e rdf:first N2088e3bde6534422abd7a01bf125b09e
91 rdf:rest N33ae81e9ab7c4282bd050d1a3067e0a7
92 Nf7214d60e6c44a0ba7caf669188414c7 schema:familyName Jansen
93 schema:givenName Klaus
94 rdf:type schema:Person
95 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
96 schema:name Mathematical Sciences
97 rdf:type schema:DefinedTerm
98 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
99 schema:name Applied Mathematics
100 rdf:type schema:DefinedTerm
101 sg:person.01274506210.27 schema:affiliation grid-institutes:grid.29857.31
102 schema:familyName Berman
103 schema:givenName Piotr
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27
105 rdf:type schema:Person
106 sg:person.015206033153.81 schema:affiliation grid-institutes:grid.116068.8
107 schema:familyName Demaine
108 schema:givenName Erik D.
109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015206033153.81
110 rdf:type schema:Person
111 sg:person.07611416301.10 schema:affiliation grid-institutes:grid.116068.8
112 schema:familyName Zadimoghaddam
113 schema:givenName Morteza
114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07611416301.10
115 rdf:type schema:Person
116 grid-institutes:grid.116068.8 schema:alternateName MIT Computer Science and Artificial Intelligence Laboratory, 32 Vassar St., 02139, Cambridge, MA, USA
117 schema:name MIT Computer Science and Artificial Intelligence Laboratory, 32 Vassar St., 02139, Cambridge, MA, USA
118 rdf:type schema:Organization
119 grid-institutes:grid.29857.31 schema:alternateName Department of Computer Science and Engineering, Pennsylvania State University, 16802, University Park, PA, USA
120 schema:name Department of Computer Science and Engineering, Pennsylvania State University, 16802, University Park, PA, USA
121 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...