Delivery by energy-constrained agents
Agents with energy budgets, placed in a weighted graph, must carry a message from a source node to a target node, handing it over when they meet: when can a planner find a schedule quickly, and by how much must the budgets grow?
Problem statement and measuresexpand
\(k\) agents start at nodes of a connected undirected graph \(G\) with \(n\) nodes and \(m\) edges; every edge \(e\) has a positive weight \(\mathrm{wt}(e)\), its length. Agent \(i\) has a budget \(B_i\): it can travel a total distance of at most \(B_i\), also along parts of edges. A message lies at a source node \(v_s\) and must reach a target node \(v_t\). An agent can pick the message up where it is, carry it, and drop it anywhere (at a node or inside an edge), where another agent can pick it up; agents need not return to their start nodes. A planner that knows \(G\), the start nodes and the budgets computes a schedule: which agents move, and where each one picks up and drops the message. The task is to decide whether a schedule exists and to find one. Time is the running time of the planner. The budget factor \(\gamma\) is that of a planner that runs in polynomial time and either correctly reports that no schedule exists or finds one in which every agent may travel \(\gamma B_i\) (resource augmentation); with equal budgets \(B_i = B\), it is the ratio between the budget the planner uses and the smallest budget that admits a schedule.
Measures: Time, running time of the planner; Budget factor, factor by which a polynomial-time planner enlarges the budgets (resource augmentation), or its approximation ratio for the smallest equal budget.
Arbitrary graphs, equal budgets
verifiedWith equal budgets, deciding whether a schedule exists stays strongly NP-hard; the smallest budget that admits a schedule can be approximated within a factor 2, and no lower bound on the factor is known.
Assumed (added on the last edge are outlined)
Not assumed
Formal definitions of this setting
- Graph dynamics: static graph
- \(G_t=G\) for all \(t\): the edge set never changes.
- Edge direction: undirected
- \(G=(V,E)\) with \(E\subseteq\binom V2\); every edge can be traversed in both directions.
- Graph class: any graph
- \(G\) is any connected undirected graph with positive edge weights.
- Budgets: equal budgets
- All agents have the same budget \(B\).
What is known
- strongly NP-complete (Theorem 1), by a reduction from 3-partition
- holds even on unweighted graphs: each agent's start node gets a pendant path of length \(B - B_i\), and the agent starts at its end
Results, in order of publication
Introductory and current best (Theorem 4). The planner tries every agent as the one that fetches the message, moves it to \(v_s\), and computes the smallest budget \(B'\) for which the reaches (the points within distance \(B'\) of the start nodes, \(B'\) minus the distance walked for the moved agent) form a chain from \(v_s\) to \(v_t\). The smallest budget that admits a schedule is at least \(B'\), and letting each agent of the chain walk to the start node of the next costs at most \(2B'\). The same idea gives budget factor 2 for the decision task.
Open questions
Is there a constant \(c > 1\) such that the smallest equal budget cannot be approximated within \(c\) in polynomial time unless P = NP? Chalopin et al. 2021 notes that no lower bound is known.
Notes
Fixed path. Chalopin, Das, Mihalák, Penna and Widmayer also fix in advance the path along which the message must travel, to keep it out of dangerous areas: the task stays NP-hard (Theorem 5, from 3SAT; the authors note that the reduction extends to equal budgets), and for some constant \(\gamma > 1\) no polynomial-time planner has budget factor \(\gamma\) unless P = NP (Corollary 2, whose proof is only sketched) Chalopin et al. 2013. Chalopin, Das, Disser, Labourel and Mihalák study it with equal budgets Chalopin et al. 2021; one agent may now carry the message on several pieces of the path. The smallest equal budget can be approximated within 3 on directed graphs (Theorem 3), not within less than 2 unless P = NP (Theorem 1), and within 2.5 on undirected graphs (Theorem 4). If every agent picks the message up at most once, the factors become 2 on directed graphs and \(2 - 1/2^k\) on undirected ones (Theorem 6), with a lower bound of 1.5 on directed graphs (Theorem 5). For two agents the fixed-path task is weakly NP-hard (Theorem 7, from subset sum); with hand-overs at nodes only, a dynamic program decides it in \(O(k\, n^{k+2} B^k)\) time for integer weights (Theorem 8) and yields a fully polynomial-time approximation scheme for a constant number of agents (Theorem 9). Several sources. With a constant number of sources, each holding data for \(v_t\), the 2-approximation extends (Theorem 6 of Chalopin et al. 2013); with arbitrarily many sources, each holding an agent, delivery is NP-hard even with equal budgets, by the convergecast reduction of Anaya et al. 2016 (Section 3.2 of Chalopin et al. 2013). Theorem numbers of Chalopin et al. 2013 refer to the authors' copy.
What carries over from neighbouring settings
Read off the order of assumptions, not checked case by case: results may carry extra assumptions (shown on their pages), and asynchronous time is measured in epochs.
Algorithms from weaker settings work here
Lower bounds from stronger settings hold here
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.