Data Delivery by Energy-Constrained Mobile Agents on a Line
dc.contributor.author
Chalopin, Jérémie
dc.contributor.author
Jacob, Riko
dc.contributor.author
Mihalák, Matúš
dc.contributor.author
Widmayer, Peter
dc.contributor.editor
Esparza, Javier
dc.contributor.editor
Fraigniaud, Pierre
dc.contributor.editor
Husfeldt, Thore
dc.contributor.editor
Koutsoupias, Elias
dc.date.accessioned
2020-10-08T13:29:40Z
dc.date.available
2017-06-11T14:49:03Z
dc.date.available
2020-10-08T13:29:40Z
dc.date.issued
2014
dc.identifier.isbn
978-3-662-43950-0
en_US
dc.identifier.isbn
978-3-662-43951-7
en_US
dc.identifier.issn
0302-9743
dc.identifier.issn
1611-3349
dc.identifier.other
10.1007/978-3-662-43951-7_36
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/94789
dc.description.abstract
We consider n mobile agents of limited energy that are placed on a straight line and that need to collectively deliver a single piece of data from a given source point s to a given target point t on the line. Agents can move only as far as their batteries allow. They can hand over the data when they meet. In this paper we show that deciding whether the agents can deliver the data is (weakly) NP-complete, and for instances where all input values are integers, we present a quasi-, pseudo-polynomial time algorithm that runs in time O(Δ2 ·n 1 + 4logΔ), where Δ is the distance between s and t. This answers an open problem stated by Anaya et al.(DISC 2012).
en_US
dc.language.iso
en
en_US
dc.publisher
Springer
en_US
dc.subject
Mobile agents and robots
en_US
dc.subject
Data aggregation and delivery
en_US
dc.subject
Power-awareness
en_US
dc.subject
Algorithms
en_US
dc.subject
Complexity
en_US
dc.title
Data Delivery by Energy-Constrained Mobile Agents on a Line
en_US
dc.type
Conference Paper
ethz.book.title
Automata, Languages, and Programming
en_US
ethz.journal.title
Lecture Notes in Computer Science
ethz.journal.volume
8573
en_US
ethz.journal.abbreviated
LNCS
ethz.pages.start
423
en_US
ethz.pages.end
434
en_US
ethz.event
41st International Colloquium on Automata, Languages, and Programming (ICALP 2014)
en_US
ethz.event.location
Copenhagen, Denmark
en_US
ethz.event.date
July 8-11, 2014
en_US
ethz.identifier.wos
ethz.identifier.nebis
010235157
ethz.publication.place
Berlin; Heidelberg
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
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 / Widmayer, Peter
ethz.date.deposited
2017-06-11T14:49:34Z
ethz.source
ECIT
ethz.identifier.importid
imp593652b2174c847017
ethz.ecitpid
pub:148887
ethz.eth
yes
en_US
ethz.availability
Metadata only
en_US
ethz.rosetta.installDate
2017-07-12T23:16:20Z
ethz.rosetta.lastUpdated
2021-02-15T17:56:50Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Data%20Delivery%20by%20Energy-Constrained%20Mobile%20Agents%20on%20a%20Line&rft.jtitle=Lecture%20Notes%20in%20Computer%20Science&rft.date=2014&rft.volume=8573&rft.spage=423&rft.epage=434&rft.issn=0302-9743&1611-3349&rft.au=Chalopin,%20J%C3%A9r%C3%A9mie&Jacob,%20Riko&Mihal%C3%A1k,%20Mat%C3%BA%C5%A1&Widmayer,%20Peter&rft.isbn=978-3-662-43950-0&978-3-662-43951-7&rft.genre=proceeding&rft_id=info:doi/10.1007/978-3-662-43951-7_36&rft.btitle=Automata,%20Languages,%20and%20Programming
Files in this item
| Files | Size | Format | Open in viewer |
|---|---|---|---|
|
There are no files associated with this item. |
|||
Publication type
-
Conference Paper [34968]