2026-08-18T03:42:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9638 2024-03-06T10:44:36Z ddc:004 open_access

Collective Fast Delivery by Energy-Efficient Agents Bärtschi, Andreas Graf, Daniel Mihalák, Matús delivery mobile agents time/energy optimization complexity algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andreas Bärtschi and Daniel Graf and Matús Mihalák 2018 Is Part Of LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2018.56 urn:nbn:de:0030-drops-96381 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.56 eng https://creativecommons.org/licenses/by/3.0/legalcode