Delivery by energy-constrained agents

\(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.