This record is currently in review state, the data hasn’t been validated yet.
- Conference Paper
We consider the problem of collaboratively delivering a package from a specified source node s to a designated target node t in an undirected graph G = (V, E), using k mobile agents. Each agent i starts at time 0 at a node p_i and can move along edges subject to two parameters: Its weight w_i, which denotes the rate of energy consumption while travelling, and its velocity v_i , which defines the speed with which agent i can travel. We are interested in operating the agents such that we minimize the total energy consumption E and the delivery time T (time when the package arrives at t). Specifically, we are after a schedule of the agents that lexicographically minimizes the tuple (E, T). We show that this problem can be solved in polynomial time O(k|V | 2 + APSP), where O(APSP) denotes the running time of an all-pair shortest-paths algorithm. This completes previous research which shows that minimizing only E or only T is polynomial-time solvable, while minimizing a convex combination of E and T, or minimizing the tuple (T, E) are both NP-hard Show more
Book titleFundamentals of Computation Theory
Journal / seriesLecture Notes in Computer Science
Organisational unit03340 - Widmayer, Peter
156620 - Algorithm Design for Microrobots with Energy Constraints (SNF)
MoreShow all metadata