Bärtschi, Andreas ;
Graf, Daniel ;
Mihalák, Matús
Collective Fast Delivery by EnergyEfficient Agents
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 + (1epsilon)* E, for a given epsilon in (0,1).
We show that (i) is solvable in polynomial time, and show that (ii) is polynomialtime solvable for uniform velocities and solvable in time O(n+k log k) for arbitrary velocities on paths, but in general is NPhard even on planar graphs. As a corollary of our hardness result, (iii) is NPhard, too. We show that there is a 2approximation algorithm for (iii) using a single agent.
BibTeX  Entry
@InProceedings{brtschi_et_al:LIPIcs:2018:9638,
author = {Andreas B{\"a}rtschi and Daniel Graf and Mat{\'u}s Mihal{\'a}k},
title = {{Collective Fast Delivery by EnergyEfficient Agents}},
booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
pages = {56:156:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770866},
ISSN = {18688969},
year = {2018},
volume = {117},
editor = {Igor Potapov and Paul Spirakis and James Worrell},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9638},
URN = {urn:nbn:de:0030drops96381},
doi = {10.4230/LIPIcs.MFCS.2018.56},
annote = {Keywords: delivery, mobile agents, time/energy optimization, complexity, algorithms}
}
27.08.2018
Keywords: 

delivery, mobile agents, time/energy optimization, complexity, algorithms 
Seminar: 

43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Issue date: 

2018 
Date of publication: 

27.08.2018 