Show simple item record

dc.contributor.author
Bärtschi, Andreas
dc.contributor.author
Chalopin, Jérémie
dc.contributor.author
Das, Shantanu
dc.contributor.author
Disser, Yann
dc.contributor.author
Graf, Daniel
dc.contributor.author
Hackfeld, Jan
dc.contributor.author
Penna, Paolo
dc.contributor.editor
Vollmer, Heribert
dc.contributor.editor
Vallée, Brigitte
dc.date.accessioned
2017-12-05T15:11:44Z
dc.date.available
2017-06-12T20:39:29Z
dc.date.available
2017-12-05T15:11:44Z
dc.date.available
2017-11-15T15:23:03Z
dc.date.available
2017-12-05T15:07:53Z
dc.date.issued
2017-03
dc.identifier.isbn
978-3-95977-028-6
en_US
dc.identifier.issn
1868-8969
dc.identifier.other
10.4230/LIPIcs.STACS.2017.10
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/218067
dc.identifier.doi
10.3929/ethz-b-000130046
dc.description.abstract
We consider the problem of delivering m messages between specified source-target pairs in an undirected graph, by k mobile agents initially located at distinct nodes of the graph. Each edge has a designated length and each agent consumes energy proportional to the distance it travels in the graph. We are interested in optimizing the total energy consumption for the team of agents. Unlike previous related work, we consider heterogeneous agents with different rates of energy consumption (weights w_i). To solve the delivery problem, agents face three major challenges: Collaboration (how to work together on each message), Planning (which route to take) and Coordination (how to assign agents to messages). We first show that the delivery problem can be 2-approximated without collaborating and that this is best possible, i.e., we show that the benefit of collaboration is 2 in general. We also show that the benefit of collaboration for a single message is 1 / log 2 which is approximately 1.44. Planning turns out to be NP-hard to approximate even for a single agent, but can be 2-approximated in polynomial time if agents have unit capacities and do not collaborate. We further show that coordination is NP-hard even for agents with unit capacity, but can be efficiently solved exactly if they additionally have uniform weights. Finally, we give a polynomial-time c-approximation for message delivery with unit capacities.
en_US
dc.language.iso
en
en_US
dc.publisher
Schloss Dagstuhl, Leibniz-Zentrum für Informatik
en_US
dc.rights.uri
http://creativecommons.org/licenses/by/3.0/
dc.subject
Approximation algorithms
en_US
dc.subject
Energy optimization
en_US
dc.subject
Message delivery
en_US
dc.subject
Mobile agents
en_US
dc.title
Energy-Efficient Delivery by Heterogeneous Mobile Agents
en_US
dc.type
Conference Paper
dc.rights.license
Creative Commons Attribution 3.0 Unported
ethz.book.title
34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
en_US
ethz.journal.title
Leibniz International Proceedings in Informatics (LIPIcs)
ethz.journal.volume
66
en_US
ethz.journal.abbreviated
LIPIcs
ethz.pages.start
10
en_US
ethz.size
14 p.
en_US
ethz.version.deposit
publishedVersion
en_US
ethz.event
34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
en_US
ethz.event.location
Hannover, Germany
en_US
ethz.event.date
March 8-11, 2017
en_US
ethz.identifier.scopus
ethz.publication.place
Dagstuhl
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03340 - Widmayer, Peter (emeritus) / Widmayer, Peter (emeritus)
en_US
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03340 - Widmayer, Peter (emeritus) / Widmayer, Peter (emeritus)
en_US
ethz.date.deposited
2017-06-12T20:40:34Z
ethz.source
ECIT
ethz.source
FORM
ethz.identifier.importid
imp59365560b41e143464
ethz.ecitpid
pub:193047
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2018-01-11T12:35:09Z
ethz.rosetta.lastUpdated
2019-02-02T13:51:56Z
ethz.rosetta.exportRequired
true
ethz.rosetta.versionExported
true
ethz.rosetta.versionExported
true
dc.identifier.olduri
http://hdl.handle.net/20.500.11850/130046
dc.identifier.olduri
http://hdl.handle.net/20.500.11850/208984
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Energy-Efficient%20Delivery%20by%20Heterogeneous%20Mobile%20Agents&rft.jtitle=Leibniz%20International%20Proceedings%20in%20Informatics%20(LIPIcs)&rft.date=2017-03&rft.volume=66&rft.spage=10&rft.issn=1868-8969&rft.au=B%C3%A4rtschi,%20Andreas&Chalopin,%20J%C3%A9r%C3%A9mie&Das,%20Shantanu&Disser,%20Yann&Graf,%20Daniel&rft.isbn=978-3-95977-028-6&rft.genre=proceeding&rft_id=info:doi/978-3-95977-028-6&rft.btitle=34th%20Symposium%20on%20Theoretical%20Aspects%20of%20Computer%20Science%20(STACS%202017)
 Search via SFX

Files in this item

Thumbnail

Publication type

Show simple item record