Show simple item record

dc.contributor.author
Bärtschi, Andreas
dc.contributor.author
Graf, Daniel
dc.contributor.author
Mihalák, Matúš
dc.contributor.editor
Potapov, Igor
dc.contributor.editor
Spirakis, Paul
dc.contributor.editor
Worrell, James
dc.date.accessioned
2018-10-18T16:42:31Z
dc.date.available
2018-10-13T07:03:04Z
dc.date.available
2018-10-18T16:42:31Z
dc.date.issued
2018
dc.identifier.isbn
978-3-95977-086-6
en_US
dc.identifier.issn
1868-8969
dc.identifier.other
10.4230/LIPIcs.MFCS.2018.56
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/295616
dc.identifier.doi
10.3929/ethz-b-000295616
dc.description.abstract
We consider k mobile agents initially located at distinct nodes of an undirected graph (on n nodes, with edge lengths). The agents have to deliver a single item from a given source node s to a given target node t. The agents can move along the edges of the graph, starting at time 0, with respect to the following: Each agent i has a weight omega_i that defines the rate of energy consumption while travelling a distance in the graph, and a velocity upsilon_i with which it can move. We are interested in schedules (operating the k agents) that result in a small delivery time T (time when the item arrives at t), and small total energy consumption E. Concretely, we ask for a schedule that: either (i) Minimizes T, (ii) Minimizes lexicographically (T,E) (prioritizing fast delivery), or (iii) Minimizes epsilon * T + (1-epsilon)* E, for a given epsilon in (0,1). We show that (i) is solvable in polynomial time, and show that (ii) is polynomial-time solvable for uniform velocities and solvable in time O(n+k log k) for arbitrary velocities on paths, but in general is NP-hard even on planar graphs. As a corollary of our hardness result, (iii) is NP-hard, too. We show that there is a 2-approximation algorithm for (iii) using a single agent.
en_US
dc.format
application/pdf
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
delivery
en_US
dc.subject
mobile agents
en_US
dc.subject
time/energy optimization
en_US
dc.subject
complexity
en_US
dc.subject
algorithms
en_US
dc.title
Collective fast delivery by energy-efficient agents
en_US
dc.type
Conference Paper
dc.rights.license
Creative Commons Attribution 3.0 Unported
ethz.book.title
43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
en_US
ethz.journal.title
Leibniz International Proceedings in Informatics (LIPIcs)
ethz.journal.volume
117
en_US
ethz.journal.abbreviated
Leibniz Int. Proc. Inform.
ethz.pages.start
56
en_US
ethz.size
16 p.
en_US
ethz.version.deposit
publishedVersion
en_US
ethz.event
43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
en_US
ethz.event.location
Liverpool, United Kingdom
en_US
ethz.event.date
August 27-31, 2018
en_US
ethz.grant
Algorithm Design for Microrobots with Energy Constraints
en_US
ethz.identifier.scopus
ethz.publication.place
Dagstuhl, Germany
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 / Widmayer, Peter
ethz.grant.agreementno
156620
ethz.grant.fundername
SNF
ethz.grant.funderDoi
10.13039/501100001711
ethz.grant.program
Projekte MINT
ethz.date.deposited
2018-10-13T07:03:19Z
ethz.source
SCOPUS
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2018-10-18T16:42:38Z
ethz.rosetta.lastUpdated
2022-03-28T21:30:16Z
ethz.rosetta.exportRequired
true
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Collective%20fast%20delivery%20by%20energy-efficient%20agents&rft.jtitle=Leibniz%20International%20Proceedings%20in%20Informatics%20(LIPIcs)&rft.date=2018&rft.volume=117&rft.spage=56&rft.issn=1868-8969&rft.au=B%C3%A4rtschi,%20Andreas&Graf,%20Daniel&Mihal%C3%A1k,%20Mat%C3%BA%C5%A1&rft.isbn=978-3-95977-086-6&rft.genre=proceeding&rft_id=info:doi/10.4230/LIPIcs.MFCS.2018.56&rft.btitle=43rd%20International%20Symposium%20on%20Mathematical%20Foundations%20%20of%20Computer%20Science%20(MFCS%202018)
 Search print copy at ETH Library

Files in this item

Thumbnail

Publication type

Show simple item record