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
standard settingverifiedDeciding whether a schedule exists is strongly NP-hard; tripling the budgets makes it polynomial, and no smaller factor does unless P = NP.
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: any budgets
- Each agent \(i\) has its own budget \(B_i\).
What is known
- strongly NP-complete (Theorem 1), by a reduction from 3-partition with polynomially bounded numbers
- holds even on unweighted graphs and with equal budgets
- no polynomial-time planner with factor \(3 - \varepsilon\), for any \(\varepsilon > 0\), unless P = NP (Theorem 6), by a reduction from 3SAT built on the planar construction
Results, in order of publication
Introductory and current best (Corollary 1). Call the points within distance \(B_i\) of agent \(i\)'s start node its reach. If no chain of agents with overlapping reaches joins \(v_s\) to \(v_t\), no schedule exists; otherwise each agent of the chain fetches the message in the reach of the previous one, returns to its start node and carries the message into the reach of the next one, which costs at most \(3B_i\) (Theorem 3). The factor \(1+\max_{i,j}B_i/B_j\) comes from the 2-approximation for equal budgets. Their \(R_i\) is \(B_i\) here, and their \(\Delta\) is \(\max_{i,j}B_i/B_j\).
Theorem 7: if the order in which the agents carry the message is fixed, the planner computes, agent by agent, the points where the message can be, in \(O(k(n+m)(n\log n + m))\) time; trying every order gives Corollary 1. Chalopin et al. 2013 had shown this when agents hand the message over only at nodes (Theorem 2). The hardness thus lies in choosing the order.
Open questions
What is the complexity of delivering several messages at once, for instance on paths? Raised in Bärtschi et al. 2020.
Notes
Returning delivery. Bärtschi, Chalopin, Das, Disser, Geissmann, Graf, Labourel and Mihalák also require every agent to come back to its start node Bärtschi et al. 2020. This variant is not a setting here, since neither variant's schedules or hardness carry over to the other. On trees it takes \(O(n + k\log k)\) time: each agent is moved to the path between \(v_s\) and \(v_t\), and the path is covered greedily by intervals of length half the remaining budget (Theorem 1). It is strongly NP-hard on planar graphs (Theorem 5), and a factor 2 suffices and is best possible unless P = NP (Theorems 2 and 6); with equal budgets a factor \(2 - 2/k\) suffices (Theorem 3). Energy exchange. If agents may hand over energy when they meet, delivery takes linear time on paths and trees but stays NP-complete on arbitrary directed and undirected graphs (Theorems 3, 7, 13 and 14 of Czyzowicz et al. 2016). Theorem numbers of Bärtschi et al. 2020 refer to its arXiv v1. 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
No catalogued weaker setting.
Lower bounds from stronger settings hold here
Branches from here
Paths
Arbitrary graphs, equal budgets
Planar graphs, equal budgets
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.