Data Delivery by Energy-Constrained Mobile Agents View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2014

AUTHORS

Jérémie Chalopin , Shantanu Das , Matúš Mihal’ák , Paolo Penna , Peter Widmayer

ABSTRACT

We consider mobile agents of limited energy, which have to collaboratively deliver data from specified sources of a network to a central repository. Every move consumes energy that is proportional to the travelled distance. Thus, every agent is limited in the total distance it can travel. We ask whether there is a schedule of agents’ movements that accomplishes the delivery. We provide hardness results, as well as exact, approximation, and resource-augmented algorithms for several variants of the problem. Among others, we show that the decision problem is NP-hard already for a single source, and we present a 2-approximation algorithm for the problem of finding the minimum energy that can be assigned to each agent such that the agents can deliver the data. More... »

PAGES

111-122

Book

TITLE

Algorithms for Sensor Systems

ISBN

978-3-642-45345-8
978-3-642-45346-5

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-45346-5_9

DOI

http://dx.doi.org/10.1007/978-3-642-45346-5_9

DIMENSIONS

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


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/0806", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information Systems", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Laboratoire d\u2019Informatique Fondamentale de Marseille", 
          "id": "https://www.grid.ac/institutes/grid.462848.4", 
          "name": [
            "LIF, Aix-Marseille University & CNRS, Marseille, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chalopin", 
        "givenName": "J\u00e9r\u00e9mie", 
        "id": "sg:person.015512567437.12", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015512567437.12"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Laboratoire d\u2019Informatique Fondamentale de Marseille", 
          "id": "https://www.grid.ac/institutes/grid.462848.4", 
          "name": [
            "LIF, Aix-Marseille University & CNRS, Marseille, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Das", 
        "givenName": "Shantanu", 
        "id": "sg:person.010565676065.53", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010565676065.53"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Swiss Federal Institute of Technology in Zurich", 
          "id": "https://www.grid.ac/institutes/grid.5801.c", 
          "name": [
            "Institute of Theoretical Computer Science, ETH Zurich, Z\u00fcrich, Switzerland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Mihal\u2019\u00e1k", 
        "givenName": "Mat\u00fa\u0161", 
        "id": "sg:person.016564106253.23", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016564106253.23"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Swiss Federal Institute of Technology in Zurich", 
          "id": "https://www.grid.ac/institutes/grid.5801.c", 
          "name": [
            "Institute of Theoretical Computer Science, ETH Zurich, Z\u00fcrich, Switzerland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Penna", 
        "givenName": "Paolo", 
        "id": "sg:person.013624103516.76", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013624103516.76"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Swiss Federal Institute of Technology in Zurich", 
          "id": "https://www.grid.ac/institutes/grid.5801.c", 
          "name": [
            "Institute of Theoretical Computer Science, ETH Zurich, Z\u00fcrich, Switzerland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Widmayer", 
        "givenName": "Peter", 
        "id": "sg:person.0757144477.93", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0757144477.93"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/978-3-642-33651-5_4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016953046", 
          "https://doi.org/10.1007/978-3-642-33651-5_4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/381677.381687", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027659236"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11672142_51", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1030708013", 
          "https://doi.org/10.1007/11672142_51"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11672142_51", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1030708013", 
          "https://doi.org/10.1007/11672142_51"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-010-9420-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1040556217", 
          "https://doi.org/10.1007/s00453-010-9420-2"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11523468_92", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049580011", 
          "https://doi.org/10.1007/11523468_92"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11523468_92", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049580011", 
          "https://doi.org/10.1007/11523468_92"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0166-218x(84)90081-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1050792184"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/comst.2006.283821", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061258155"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tsmca.2004.838486", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061795032"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s0097539791194931", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062879656"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s009753979732428x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062880193"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2014", 
    "datePublishedReg": "2014-01-01", 
    "description": "We consider mobile agents of limited energy, which have to collaboratively deliver data from specified sources of a network to a central repository. Every move consumes energy that is proportional to the travelled distance. Thus, every agent is limited in the total distance it can travel. We ask whether there is a schedule of agents\u2019 movements that accomplishes the delivery. We provide hardness results, as well as exact, approximation, and resource-augmented algorithms for several variants of the problem. Among others, we show that the decision problem is NP-hard already for a single source, and we present a 2-approximation algorithm for the problem of finding the minimum energy that can be assigned to each agent such that the agents can deliver the data.", 
    "editor": [
      {
        "familyName": "Flocchini", 
        "givenName": "Paola", 
        "type": "Person"
      }, 
      {
        "familyName": "Gao", 
        "givenName": "Jie", 
        "type": "Person"
      }, 
      {
        "familyName": "Kranakis", 
        "givenName": "Evangelos", 
        "type": "Person"
      }, 
      {
        "familyName": "Meyer auf der Heide", 
        "givenName": "Friedhelm", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-45346-5_9", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-45345-8", 
        "978-3-642-45346-5"
      ], 
      "name": "Algorithms for Sensor Systems", 
      "type": "Book"
    }, 
    "name": "Data Delivery by Energy-Constrained Mobile Agents", 
    "pagination": "111-122", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-45346-5_9"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "da6752e10f014f0b781ef921e3bf2dcb151ce71f3ef10356b60e518511ade06b"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1045850213"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-45346-5_9", 
      "https://app.dimensions.ai/details/publication/pub.1045850213"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T10:37", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8659_00000271.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/978-3-642-45346-5_9"
  }
]
 

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-45346-5_9'

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-45346-5_9'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-45346-5_9'

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-45346-5_9'


 

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

145 TRIPLES      23 PREDICATES      37 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-45346-5_9 schema:about anzsrc-for:08
2 anzsrc-for:0806
3 schema:author Nbc9d40c71d804bc3a78a71a13a2c5158
4 schema:citation sg:pub.10.1007/11523468_92
5 sg:pub.10.1007/11672142_51
6 sg:pub.10.1007/978-3-642-33651-5_4
7 sg:pub.10.1007/s00453-010-9420-2
8 https://doi.org/10.1016/0166-218x(84)90081-7
9 https://doi.org/10.1109/comst.2006.283821
10 https://doi.org/10.1109/tsmca.2004.838486
11 https://doi.org/10.1137/s0097539791194931
12 https://doi.org/10.1137/s009753979732428x
13 https://doi.org/10.1145/381677.381687
14 schema:datePublished 2014
15 schema:datePublishedReg 2014-01-01
16 schema:description We consider mobile agents of limited energy, which have to collaboratively deliver data from specified sources of a network to a central repository. Every move consumes energy that is proportional to the travelled distance. Thus, every agent is limited in the total distance it can travel. We ask whether there is a schedule of agents’ movements that accomplishes the delivery. We provide hardness results, as well as exact, approximation, and resource-augmented algorithms for several variants of the problem. Among others, we show that the decision problem is NP-hard already for a single source, and we present a 2-approximation algorithm for the problem of finding the minimum energy that can be assigned to each agent such that the agents can deliver the data.
17 schema:editor N26d010c9f96848aeb9aae0ea8d94c0b7
18 schema:genre chapter
19 schema:inLanguage en
20 schema:isAccessibleForFree false
21 schema:isPartOf Ne19409c67c1e4e03827dcba3aa53a254
22 schema:name Data Delivery by Energy-Constrained Mobile Agents
23 schema:pagination 111-122
24 schema:productId N5f6c1ae161664b229b82f5cf31e15636
25 N72282af4ac5745f08814b226fe107504
26 Na48f1561beb343b2a1b56edf107fc296
27 schema:publisher N4b45d645a5b544d69bb2c1efd13b6275
28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045850213
29 https://doi.org/10.1007/978-3-642-45346-5_9
30 schema:sdDatePublished 2019-04-15T10:37
31 schema:sdLicense https://scigraph.springernature.com/explorer/license/
32 schema:sdPublisher Nd5348a39272b46fda140beca10b8ccac
33 schema:url http://link.springer.com/10.1007/978-3-642-45346-5_9
34 sgo:license sg:explorer/license/
35 sgo:sdDataset chapters
36 rdf:type schema:Chapter
37 N13193f561f9c40dca0e78d128eea509a rdf:first sg:person.013624103516.76
38 rdf:rest N79f15d474c6e4f16b54c9576447b4481
39 N26d010c9f96848aeb9aae0ea8d94c0b7 rdf:first Na59e3473900b4a66b589c08029d3192d
40 rdf:rest N8bcceb7c484e48339bd78ccd40674780
41 N2d4370bb8edb405da59cbc3e353240f7 rdf:first sg:person.010565676065.53
42 rdf:rest N4de48694598647b3b00f780b0123f6be
43 N37d7d2a1b52d433ca7a18e8267765b2e schema:familyName Kranakis
44 schema:givenName Evangelos
45 rdf:type schema:Person
46 N3dd753a6908f4fab9d26335b389ea4b0 rdf:first N37d7d2a1b52d433ca7a18e8267765b2e
47 rdf:rest N69704bed09d240d5aa0667819a45a389
48 N4b45d645a5b544d69bb2c1efd13b6275 schema:location Berlin, Heidelberg
49 schema:name Springer Berlin Heidelberg
50 rdf:type schema:Organisation
51 N4de48694598647b3b00f780b0123f6be rdf:first sg:person.016564106253.23
52 rdf:rest N13193f561f9c40dca0e78d128eea509a
53 N5f6c1ae161664b229b82f5cf31e15636 schema:name doi
54 schema:value 10.1007/978-3-642-45346-5_9
55 rdf:type schema:PropertyValue
56 N69704bed09d240d5aa0667819a45a389 rdf:first N70a5b99517314d249339e5b2645e582c
57 rdf:rest rdf:nil
58 N70a5b99517314d249339e5b2645e582c schema:familyName Meyer auf der Heide
59 schema:givenName Friedhelm
60 rdf:type schema:Person
61 N72282af4ac5745f08814b226fe107504 schema:name dimensions_id
62 schema:value pub.1045850213
63 rdf:type schema:PropertyValue
64 N75e6851c7cfa4046a92cbd3e3557ad76 schema:familyName Gao
65 schema:givenName Jie
66 rdf:type schema:Person
67 N79f15d474c6e4f16b54c9576447b4481 rdf:first sg:person.0757144477.93
68 rdf:rest rdf:nil
69 N8bcceb7c484e48339bd78ccd40674780 rdf:first N75e6851c7cfa4046a92cbd3e3557ad76
70 rdf:rest N3dd753a6908f4fab9d26335b389ea4b0
71 Na48f1561beb343b2a1b56edf107fc296 schema:name readcube_id
72 schema:value da6752e10f014f0b781ef921e3bf2dcb151ce71f3ef10356b60e518511ade06b
73 rdf:type schema:PropertyValue
74 Na59e3473900b4a66b589c08029d3192d schema:familyName Flocchini
75 schema:givenName Paola
76 rdf:type schema:Person
77 Nbc9d40c71d804bc3a78a71a13a2c5158 rdf:first sg:person.015512567437.12
78 rdf:rest N2d4370bb8edb405da59cbc3e353240f7
79 Nd5348a39272b46fda140beca10b8ccac schema:name Springer Nature - SN SciGraph project
80 rdf:type schema:Organization
81 Ne19409c67c1e4e03827dcba3aa53a254 schema:isbn 978-3-642-45345-8
82 978-3-642-45346-5
83 schema:name Algorithms for Sensor Systems
84 rdf:type schema:Book
85 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
86 schema:name Information and Computing Sciences
87 rdf:type schema:DefinedTerm
88 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
89 schema:name Information Systems
90 rdf:type schema:DefinedTerm
91 sg:person.010565676065.53 schema:affiliation https://www.grid.ac/institutes/grid.462848.4
92 schema:familyName Das
93 schema:givenName Shantanu
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010565676065.53
95 rdf:type schema:Person
96 sg:person.013624103516.76 schema:affiliation https://www.grid.ac/institutes/grid.5801.c
97 schema:familyName Penna
98 schema:givenName Paolo
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013624103516.76
100 rdf:type schema:Person
101 sg:person.015512567437.12 schema:affiliation https://www.grid.ac/institutes/grid.462848.4
102 schema:familyName Chalopin
103 schema:givenName Jérémie
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015512567437.12
105 rdf:type schema:Person
106 sg:person.016564106253.23 schema:affiliation https://www.grid.ac/institutes/grid.5801.c
107 schema:familyName Mihal’ák
108 schema:givenName Matúš
109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016564106253.23
110 rdf:type schema:Person
111 sg:person.0757144477.93 schema:affiliation https://www.grid.ac/institutes/grid.5801.c
112 schema:familyName Widmayer
113 schema:givenName Peter
114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0757144477.93
115 rdf:type schema:Person
116 sg:pub.10.1007/11523468_92 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049580011
117 https://doi.org/10.1007/11523468_92
118 rdf:type schema:CreativeWork
119 sg:pub.10.1007/11672142_51 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030708013
120 https://doi.org/10.1007/11672142_51
121 rdf:type schema:CreativeWork
122 sg:pub.10.1007/978-3-642-33651-5_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016953046
123 https://doi.org/10.1007/978-3-642-33651-5_4
124 rdf:type schema:CreativeWork
125 sg:pub.10.1007/s00453-010-9420-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040556217
126 https://doi.org/10.1007/s00453-010-9420-2
127 rdf:type schema:CreativeWork
128 https://doi.org/10.1016/0166-218x(84)90081-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050792184
129 rdf:type schema:CreativeWork
130 https://doi.org/10.1109/comst.2006.283821 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061258155
131 rdf:type schema:CreativeWork
132 https://doi.org/10.1109/tsmca.2004.838486 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061795032
133 rdf:type schema:CreativeWork
134 https://doi.org/10.1137/s0097539791194931 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062879656
135 rdf:type schema:CreativeWork
136 https://doi.org/10.1137/s009753979732428x schema:sameAs https://app.dimensions.ai/details/publication/pub.1062880193
137 rdf:type schema:CreativeWork
138 https://doi.org/10.1145/381677.381687 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027659236
139 rdf:type schema:CreativeWork
140 https://www.grid.ac/institutes/grid.462848.4 schema:alternateName Laboratoire d’Informatique Fondamentale de Marseille
141 schema:name LIF, Aix-Marseille University & CNRS, Marseille, France
142 rdf:type schema:Organization
143 https://www.grid.ac/institutes/grid.5801.c schema:alternateName Swiss Federal Institute of Technology in Zurich
144 schema:name Institute of Theoretical Computer Science, ETH Zurich, Zürich, Switzerland
145 rdf:type schema:Organization
 




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


...