Jérémie Chalopin
email: jeremie.chalopin@lis-lab.fr

Shantanu Das
email: shantanu.das@lis-lab.fr

Yann Disser
email: disser@mathematik.tu-darmstadt.de

Arnaud Labourel
email: arnaud.labourel@lis-lab.fr

Matúš Mihalák
email: matus.mihalak@maastrichtuniversity.nl

Collaborative delivery on a fixed path with homogeneous energy-constrained agents

Keywords: Collaborative delivery, mobile agents, energy constrained robots, directed graphs, fixed path, approximation algorithms

come

Introduction

We consider a team of mobile agents which need to collaboratively deliver a package from a source location to a destination. The difficulty of collaboration can be due to several limitations of the agents, such as limited communication, restricted vision or the lack of persistent memory, and this has been the subject of extensive research (see e.g. [START_REF]Distributed Computing by Mobile Entities[END_REF] for a recent survey of this area of research). When considering agents that move physically (such as mobile robots or automated vehicles), a major limitation of the agents are their energy resources, which restricts the distance that the robot can travel. This is particularly true for small battery operated robots or drones, for which the energy limitation is the real bottleneck. We consider a set of mobile agents where each agent i has a budget B i on the distance it can move, as in [START_REF] Anaya | Convergecast and broadcast by power-aware mobile agents[END_REF][START_REF] Bärtschi | Collaborative delivery with energy-constrained mobile robots[END_REF][START_REF] Chalopin | Data delivery by energy-constrained mobile agents[END_REF][START_REF] Chalopin | Data delivery by energyconstrained mobile agents on a line[END_REF][START_REF] Das | Collaborative exploration by energyconstrained mobile robots[END_REF][START_REF] Dynia | Power-aware collective tree exploration[END_REF]. We model the environment as a directed or undirected edge-weighted graph G, with each agent starting on some vertex of G and traveling along edges of G, until it runs out of energy and stops forever. In this model, the agents are obliged to collaborate as no single agent can usually perform the required task on its own. Given a graph G with designated source and target vertices, and k agents with given starting locations and energy budgets, the decision problem of whether the agents can collectively deliver a single package from the source to the target node in G is called CollaborativeDelivery. Chalopin et al. [START_REF] Chalopin | Data delivery by energy-constrained mobile agents[END_REF][START_REF] Chalopin | Data delivery by energyconstrained mobile agents on a line[END_REF] showed that CollaborativeDelivery is weakly NP-hard on paths and strongly NP-hard on general graphs. When the agents are homogenous, each agent has the same uniform budget initially. The optimization version of this problem asks for the minimum energy budget B per agent, that allows a feasible schedule for delivering the package. Throughout this paper we consider agents with uniform budgets. There exist constant factor approximations [START_REF] Bärtschi | Collaborative delivery with energy-constrained mobile robots[END_REF][START_REF] Chalopin | Data delivery by energy-constrained mobile agents[END_REF] for the optimal budget needed for solving CollaborativeDelivery.

Unlike previous papers, this paper considers a version of the problem where the package must be transported through a designated path that is provided as input to the algorithm. This is a natural assumption, e.g. for delivery of valuable packages which must go on a "safe" route, allowing them to be tracked. We call this variant FixedPath CollaborativeDelivery. Even with this additional constraint, the problem remains NP-hard for general graphs due to the result in [START_REF] Chalopin | Data delivery by energy-constrained mobile agents[END_REF]. Note that on trees, the two problems are equivalent and both problems are known to be weakly NP-hard. However, for arbitrary graphs, the two problems are quite different. In particular, in the FixedPath CollaborativeDelivery, each agent may be used multiple times, while in the original version each agent participates at most once in any optimal delivery schedule (see [START_REF] Chalopin | Data delivery by energy-constrained mobile agents[END_REF]). In this paper, we attempt to find the difference between the two problems in terms of approximability.

Our Model.

We consider finite, connected (or strongly connected), edge-weighted graphs G = (V, E) with n = |V | vertices. For undirected graphs, the weight w(e) of an edge e ∈ E defines the energy required to cross the edge in either direction. For directed graphs, there may be up to two directed arcs between any pair of vertices and the weight of each arc is the energy required to traverse the arc from its tail to its head. We have k mobile agents which are initially placed on arbitrary nodes p 1 , . . . , p k of G, called the starting positions. In this paper, we consider the agents to have uniform budget B. Each agent has an initially assigned energy budget B > 0 which allows each agent to move along the edges of the graph for a total distance of at most B (if an agent travels only on a part of an edge, its travelled distance is downscaled proportionally to the part travelled). The agents are required to move a package from a given source node s to a target node t. An agent can pick up the package when it is at the same location as the package; we say that the agent is carrying the package. An agent carrying the package can drop it at any location that it visits, i.e., either at a node or even at a point inside an edge/arc. The agents do not need to return to their starting locations, after completing their task. We assume that the graph and the starting locations are initially known and the objective is to compute a strategy for movements of the agents which allows the delivery of the package from s to t (along a given (s, t) path P ). We denote by d(x, y) = d G (x, y) the distance between two nodes x, y in G (i.e. the sum of the weights on the shortest path from x to y in G). The length of path P is the sum of the weights on the path, denoted by w(P ) = d P (s, t). We denote an interval on this path as (x, y] if it includes all points on P between x and y, excluding point x, but including y.

Definitions. Given a graph G with edge-weights w, vertices s = t ∈ V (G), starting nodes p 1 , . . . , p k for the k agents, and an energy budget B, we define CollaborativeDelivery as the decision problem of whether the agents can collectively deliver the package. A solution to CollaborativeDelivery is given in the form of a delivery schedule which prescribes for each agent whether it moves and if so, the locations in which it has to pick up and drop off the package. A delivery schedule is feasible if the package can be delivered from s to t and each agent moves at most distance B.

The optimization version of CollaborativeDelivery is to compute the minimum value of B for which there exists a feasible delivery schedule. The problem of FixedPath CollaborativeDelivery provides an additional parameter: an (s, t) path P in G, and the feasible delivery schedules are restricted to those where the package travels on the given path P . Thus an instance of FixedPath CollaborativeDelivery is given as (G, w, P, p 1 , . . . , p k ) where P is a path in G, starting at node s and ending at node t.

Related Work.

The model of energy-constrained robot was introduced by Betke et al. [START_REF] Betke | Piecemeal learning of an unknown environment[END_REF] for single agent exploration of grid graphs. Later Awerbuch et al. [START_REF] Awerbuch | Piecemeal graph exploration by a mobile robot[END_REF] studied the same problem for general graphs. In both these papers, the agent is allowed to return to its starting node to refuel, and between two visits to the starting node the agent can traverse at most B edges. Duncan et al. [START_REF] Duncan | Optimal constrained graph exploration[END_REF] studied a similar model where the agent is tied with a rope of length B to the starting location and they optimized the exploration time, giving an O(m) time algorithm. A more recent paper [START_REF] Das | Energy constrained depth first search[END_REF] provides a constant competitive algorithm for the same exploration problem when the value of energy budget B may be as small as the length of the smallest path that visits the farthest node.

For energy-constrained agents without the option of refuelling, multiple agents may be needed to explore even graphs of restricted diameter. Given a graph G and k agents starting from the same location, each having an energy constraint of B, deciding whether G can be explored by the agents is NP-hard, even if graph G is a tree [START_REF] Fraigniaud | Collective tree exploration[END_REF]. Dynia et al. studied the online version of the problem [START_REF] Dynia | Power-aware collective tree exploration[END_REF][START_REF] Dynia | Why robots need maps[END_REF]. They presented algorithms for exploration of trees by k agents when the energy of each agent is augmented by a constant factor over the minimum energy B required per agent in the offline solution. Das et al. [START_REF] Das | Collaborative exploration by energyconstrained mobile robots[END_REF] presented online algorithms that optimize the number of agents used for tree exploration when each agent has a fixed energy bound B. On the other hand, Dereniowski et al. [START_REF] Dereniowski | Fast collaborative graph exploration[END_REF] gave an optimal time algorithm for exploring general graphs using a large number of agents. When both k and B are fixed, Bampas et al. [START_REF] Bampas | Maximal exploration of trees with energy-constrained agents[END_REF] studied the problem of maximizing the number of nodes explored by the agents, called the maximal exploration problem. For more details on tree exploration with energy constraint, see the recent thesis [START_REF] Karousatou | Distributed algorithms for energy constrained mobile agents[END_REF].

When multiple agents start from arbitrary locations in a graph, optimizing the total energy consumption of the agents is computationally hard for several formation problems which require the agents to place themselves in desired configurations (e.g. connected or independent configurations) in a graph [START_REF] Demaine | Minimizing movement[END_REF][START_REF] Bilò | Polygonconstrained motion planning problems[END_REF]. Anaya et al. [START_REF] Anaya | Convergecast and broadcast by power-aware mobile agents[END_REF] studied centralized and distributed algorithms for the information exchange by energy-constrained agents, in particular the problem of transferring information from one agent to all others (Broadcast) and from all agents to one agent (Convergecast). For both problems, they provided hardness results for trees and approximation algorithms for arbitrary graphs. Czyzowicz et al. [START_REF] Czyzowicz | Communication problems for mobile agents exchanging energy[END_REF] recently showed that the problems of collaborative delivery, broadcast and convergecast remain NP-hard for general graphs even if the agents are allowed to exchange energy when they meet. Further results on collective delivery with energy exchange showed that the problem remains hard even when B is a small constant [START_REF] Bampas | Collaborative delivery by energy-sharing low-power mobile robots[END_REF].

As mentioned before, the collaborative delivery problem was first studied by Chalopin et al. [START_REF] Chalopin | Data delivery by energy-constrained mobile agents[END_REF] in arbitrary undirected graphs for both uniform or nonuniform budgets. When the agents have non-uniform budgets, they provided the so-called resource-augmented algorithms where the budgets of the agents are augmented by a small constant factor to allow polynomial time solutions for all feasible instances of the original problem. The surprising result that collaborative delivery non-uniform budgets is weakly NP-hard even for a line was proved in [START_REF] Chalopin | Data delivery by energyconstrained mobile agents on a line[END_REF] where a quasi-pseudo-polynomial time algorithm was provided.

Bärtschi et al. [START_REF] Bärtschi | Collaborative delivery with energy-constrained mobile robots[END_REF] considered the returning version of the problem, where each agent needs to return to its starting location. They showed that, in this case, the problem can be solved in polynomial time for trees, but the problem is still NP-hard for arbitrary planar graphs. They provided 2-resource-augmented algorithm for general graphs in this setting and showed that it is the best possible solution that can be computed in polynomial time. Other variants of collaborative delivery that have been considered are when agents have distinct rate of energy consumption [START_REF] Bärtschi | Energy-efficient delivery by heterogeneous mobile agents[END_REF] or when the agents have distinct speeds [START_REF] Bärtschi | Collective Fast Delivery by Energy-Efficient Agents[END_REF]. In these cases the optimization criteria is to minimize the total energy consumption and/or the total time taken for delivery. Another related work [START_REF] Bärtschi | Truthful Mechanisms for Delivery with Agents[END_REF] studied the collective delivery problem for selfish agents that try to optimize their personal gain. See also [START_REF] Bärtschi | Efficient delivery with mobile agents[END_REF] for a survey of recent results on collaborative delivery by agents with energy limitations.

Our Contributions.

We show that the best possible approximation of the optimal budget B for FixedPath CollaborativeDelivery is between 2 and 3 for directed graphs and at most 2.5 for undirected graphs. In contrast, the best known approximation ratio for the general version of CollaborativeDelivery is 2 for undirected graphs [START_REF] Chalopin | Data delivery by energy-constrained mobile agents[END_REF], and there is no known lower bound on approximability.

In the fixed path version of the problem agents may be used multiple times in a feasible delivery schedule, i.e., the same agent may move the package along several disjoint segments of the path. Thus, it is not surprising that our solution for FixedPath CollaborativeDelivery has a higher approximation ratio than the general version of the problem where each agent is used at most once.

For better comparison, we can make the FixedPath CollaborativeDelivery problem easier by restricting each agent to a single pickup of the package. This easier version of the problem was considered recently in [START_REF] Giannakos | Data delivery by mobile agents with energy constraints over a fixed path[END_REF] which provided a 3-approximation algorithm. In this paper we improve upon this and provide a 2-approximation algorithm for directed graphs and a (2 -1/2 k )-approximation algorithm for undirected graphs. We also show that there exists no polynomial-time approximation algorithm with better approximation ratio than 3 2 for directed graphs.

Finally, for the case where the number of agents k is a constant, we show that the decision version of FixedPath CollaborativeDelivery can be solved in pseudo-polynomial time. For this setting, we also provide a fully polynomial-time approximation scheme (FPTAS) giving a (1 + )-approximation to the optimal budget, for any > 0.

Lower bound on approximation

In this section we prove a lower bound on the approximation factor for any polynomial time algorithm that solves collaborative delivery with uniform budgets on a fixed path.

We give a reduction from an NP-hard variant of Sat [START_REF] Garey | Computers and intractability: A Guide to the Theory of NP-Completeness[END_REF]. Note the difference from the polynomially solvable (3, 3)-Sat, where each variable appears in exactly three clauses [START_REF] Tovey | A simplified np-complete satisfiability problem[END_REF].

(≤ 3, 3)-Sat Input: A formula with a set of clauses C of size three over a set of variables X, where each variable appears in at most three clauses. Problem: Is there a truth assignment of X satisfying C?

Observe that we may assume that each variable appears at most twice in positive literals and exactly once in a negative literal, otherwise we can either eliminate or negate the variable.

Theorem 1. The minimum uniform budget required to solve FixedPath Col-laborativeDelivery on directed graphs cannot be approximated to within a factor better than 2 in polynomial time, unless P = NP.

Proof We reduce from (≤ 3, 3)-Sat by constructing, for every sufficiently small ε > 0 and every instance of (≤ 3, 3)-Sat, an instance of FixedPath CollaborativeDelivery that has a solution with budget B ≤ 2 -ε if and only if the (≤ 3, 3)-Sat instance has a satisfying assignment. In this case, our instance always admits a solution with budget B = 1. Since (≤ 3, 3)-Sat is NP-hard, this then implies that no (2 -ε)-approximation algorithm can exist, unless P = NP.

In the following, fix 0 < ε < 1 and consider an instance of (≤ 3, 3)-Sat with variables x 1 , . . . , x t and clauses C 1 , . . . , C m . We construct a (directed) instance of FixedPath CollaborativeDelivery with k = (3 + q)t agents, where q := 3/ε , starting at vertices p 1 , . . . , p k . The agents 3i -2, 3i -1, 3i for i ∈ {1, . . . , t} are associated with the (at most) two positive literals and the single negative literal of variable x i , in this order, that appear in the clauses. In case variable x i only appears in a single positive literal, the agent 3i -1 does not represent any literal. The other q •t agents are the so-called blockers, defined later. We incrementally construct the fixed (s, t)-path P = (s = v 0 , v 1 , . . . , v m+2(q+1)t ) that the package has to be transported along.

The first m arcs of P correspond to the clauses C 1 , . . . , C m . Each arc e = (v j-1 , v j ) with j ∈ {1, . . . , m} has weight w(e) = 1 and is associated with clause C j . For every literal of a variable x i that appears in C j , we let p ij denote the starting position of the (unique) agent associated with this literal, and we introduce an arc e ij = (p ij , v j-1 ) of weight w(e ij ) = 0. Now we add the variable gadgets to the path P . Let q i := m + 2(q + 1)(i -1). The gadget associated with each variable x i (cf. Figure 1) is the subpath P i = (v qi , . . . , v qi+1 ) of P consisting of 2q + 2 edges. The first q arcs have weight ε/3 p 3i-2 p 3i p 3i-1 each, the central two arcs e i = (v qi+q , v qi+q+1 ) and e i = (v qi+q+1 , v qi+q+2 ) have weights w(e i ) = ε/3 and w(e i ) = 1 -ε/3, and the final q arcs have weight 1 -ε/3 each. For ∈ {1, . . . , q}, we connect the starting position of the ((i -1)q + )-th blocker to v qi+ -1 with an arc of weight 0, and we add a shortcut arc (that cannot be taken by the package) (v qi+ , v qi+1-) of weight 0. Finally, we connect the three agents associated with variable x i as follows: We add an arc (p 3i-2 , v qi+q ) of weight 1 -ε/3, an arc (p 3i-1 , v qi+q+1 ) of weight ε/3, and an arc (p 3i , v qi+q ) of weight 0.

ε 3 ε 3 ε 3 ε 3 1 -ε 3 1 -ε 3 1 -ε 3 1 -ε 3 0 0 0 0 1 -ε/3 0 ε/3
We first claim that in every solution with B ≤ 2 -ε we can assume that, without loss of generality, for every i ∈ {1, . . . , t} and every ∈ {1, . . . , q}, the ((i-1)q+ )-th blocker transports the package across the arc (v qi+ -1 , v qi+ ), then takes the shortcut arc (v qi+ , v qi+1-), and finally transports the package across the arc (v qi+1-, v qi+1-+1 ). To see this, consider the last arc (v qi+1-1 , v qi+1 ) of P i . Since the arcs preceding the vertices v qi and v qi+1-1 along P both have length at least 1 -ε/3, no agent other than the two blockers connected to v qi and v qi+1 can reach v qi+1-1 with more than B -(1 -ε/3) ≤ 1 -2ε/3 budget remaining, which is insufficient to cross the last arc of P i . Since there is no disadvantage in using the ((i-1)q +1)-st blocker rather than the ((i-1)q +2)-nd, we may assume that the ((i-1)q +1)-st blocker transports the package as claimed. By repeating this argument (slightly adapted for the iq-th blocker), we can fix all subsequent blockers, too. Note that each blocker requires only B = 1.

After fixing all blockers, we can observe that any other agent, having a budget B ≤ 2 -ε can transport the package either inside a single clause gadget or inside a single variable gadget, but not both. This is because transporting the package inside a clause gadget requires one unit of budget, and entering/leaving a variable gadget before or after transporting the package across one of its two central arcs also takes at least one unit of budget (all other arcs of a variable gadget are handled by blockers).

Finally, and crucially, observe that, in order to transport the package across the two central edges of the variable gadget for x i , either the two agents 3i -2 and 3i -1 associated with the positive literals of x i , or the agent 3i associated with the negative literal are needed, since blockers cannot help (see above). We interpret the former situation as x i being set to false, and the latter situation as x i being set to true. Note that either assignment can be accomplished with B = 1.

If a variable is set to true, the two agents corresponding to positive literals are free to transport the package across the single (!) clause gadget each of them can reach. Otherwise, the agent corresponding to the negative literal is free to do this. In both cases, we interpret this as the clause being satisfied by the corresponding variable. Note that satisfying a clause again requires only B = 1.

Clearly, we can turn a satisfying assignment for (≤ 3, 3)-Sat into a feasible solution of FixedPath CollaborativeDelivery with B = 1. Conversely, every feasible solution of FixedPath CollaborativeDelivery with B ≤ 2 -ε corresponds to a satisfying assignment for (≤ 3, 3)-Sat. Note that q is constant for fixed ε, hence our construction can be done in polynomial time.

Approximation algorithms for fixed path delivery

In this section, we give approximation algorithms solving FixedPath Col-laborativeDelivery for both directed and undirected graphs. Note that for solution to the problem the total distance travelled by the agents must be at least the length of the path P plus the distance to s from the closest agent (which denote this by D). This gives the following bound on the optimal budget per agent.

Observation 2. The optimal budget B for FixedPath CollaborativeDelivery must be in the range [D/k, D], where D = min i d G (p i , s) + w(P ).

In the following, we assume that we are given the optimal value of B for a given instance of the problem and we provide a polynomial time algorithm to compute a delivery strategy that uses an energy budget of at most α • B for some constant α > 1. When B is not known, we can guess the optimal value of B by using a binary search in the interval [D/k, D] due to the above observation. The binary search terminates when we find the smallest B for which our algorithm provides a valid strategy for a budget of α • B. Clearly this provides an α-approximation algorithm for the optimization problem.

Consider an optimal solution to the problem which moves the package on path P using a budget of B per agent. If P is of length at least l • B then at least l agents were used. Consider a partition of the path P into intervals of length B exactly (assuming that w(P ) is a multiple of B). Then, for any x ≤ l intervals, there must be at least x agents that pushed the package along those intervals in any optimal solution. This means that it is possible to assign agents to intervals in such a way that: (i) The agent assigned to the interval participated in moving the package on that interval, i.e. the agent is able to reach some point on the interval using at most budget B. (ii) Each agent is assigned a distinct interval.

The solution strategies that we use for the approximation algorithm would use the above idea. In particular we would try to find a matching between a subset of the agents and the intervals of the path P as described below.

Lemma 1. Given an instance (G, w, P, p 1 , . . . , p k ) of the problem for which the optimal budget is B and B < w(P ), let, for some l ≥ 2, m 0 , m 1 , . . . , m l-1 be distinct points (not necessarily vertices) on the path P , such that 0 ≤ d P (s, m 0 ) < B, d P (m i-1 , m i ) = B, for 0 < i < l, and d P (m l-1 , t) > 0. We consider the path P as an Euclidean line and on this line, we define I 0 to be the interval [s,s] and I i to be the interval (m i-1 , m i ], for 0 < i < l. Then there exists distinct agents a 0 , a 1 , . . . , a l-1 which can be matched to interval I 0 , I 1 , . . . I l-1 , such that each agent a i can reach some point in interval I i using an energy budget of at most B.

Proof Note that for moving the package across x segments of length B each, we need at least x agents. Consider any optimal solution for the instance and let a 0 be the agent that picks up the package at source s, which implies agent a 0 was able to reach s. If d P (s, m 0 ) > 0, and agent a 0 moves the package over some non-zero distance in this interval, it would have depleted some of its energy; thus agent a 0 would not have enough energy to move the package over the complete interval I 1 , which is of length B. Thus, at least one other agent must participate in moving the package over interval I 1 , let this be agent a 1 . On the other hand, if d P (s, m 0 ) = 0, i.e. s = m 0 , then agent a 0 can potentially move the package on the complete interval I 1 ; in that case it would completely exhaust its budget and there must be some other agent a 1 that picks up the package at m 1 . This implies agent a 1 was able to reach point m 1 ∈ I 1 . So, in both cases there is an agent a 1 that can reach I 1 . Thus, the lemma holds for the base case of l = 2 and we can extend this argument. Suppose the lemma holds for l = j and agents a 0 , . . . a j-1 be the corresponding agents. We prove the lemma for l = j + 1 i.e. for j intervals I 1 to I j .

Case(i): Only the j agents a 0 , . . . a j-1 move the package over intervals I 0 to I j in the optimal solution. This is only possible if s = m 0 and each agent starts at the beginning of an interval. In this case the j agents would completely exhaust their total budget in moving the package and thus, a new agent a j must pick up the package at m j (Note that that target t is further than point m j according to the lemma). Thus, we have agents a 0 , . . . a j that satisfy the conditions of the lemma.

Case(ii): There are x ≥ j + 1 agents a 0 , . . . a x that participate in the optimal solution, with agents a 0 to a j-1 already matched to the intervals I 0 to I j-1 , according to the induction hypothesis. Consider the last interval I j and let A * be the subset of i > 0 agents that participated in moving the package on this particular interval. If one of these agents is unmatched, it can matched to interval I j and we are done. Otherwise the agents in A * are matched to i intervals, possibly including the interval [s, s], so the total length of these intervals is at most (i -1) * B. If we include the interval I j of length B and consider the fact that some of the agents have to move between non-consecutive intervals incurring additional energy consumption, this implies that the total movement by all the agents that participated in these (i + 1) intervals is strictly more than i * B. Hence, at least one other agent a r / ∈ A * participated in at least one of these intervals say, I q , where q < j. If we match this agent to interval I q , then the agent a q that was originally matched to I q , can be matched to interval I j . By definition a q ∈ A * and thus participated in the last interval I j , so it can reach I j . This concludes the proof.

The solution strategies that we use for the approximation algorithm would use the above fact. We first show that it is possible to compute in polynomial time, one such matching between a subset of agents and the segments of the path P as defined in the Lemma 1.

Lemma 2. Consider an instance (G, w, P, p 1 , . . . , p k ) of the problem for which the optimal budget is B, then given any set I = I 0 , I 1 , . . . I l of segments of P satisfying the conditions of Lemma 1, there is a O(n 3 ) algorithm to find a matching g between the a subset of agents and the segments, satisfying Lemma 1.

Proof One can find such a matching g using the following algorithm : 1. Construct a weighted bipartite graph

H = (A ∪ I, E, w H ) with A = [0, k], M = [0, ], E = M × A and for all i ∈ M, j ∈ A, w H (ij)
is the smallest distance from p j (the starting position of agent j) to some vertex in I i (or one of the endpoints of I i in case no vertex is located in that segment). This can be done in O(k(m + n log n)) using a Dijkstra's algorithm [START_REF] Fredman | Fibonacci heaps and their uses in improved network optimization algorithms[END_REF] starting from each starting position of an agent. Observe that graph H has O(n + k) vertices and O(k(n + k)) edges. 2. Compute a maximal matching in H that minimizes the maximum weight.

For each weight ω, one can compute in time O((n + k) 2 log(n + k) + k(n + k) min(n, k)) a maximal matching [START_REF] Fredman | Fibonacci heaps and their uses in improved network optimization algorithms[END_REF] in the graph H without edges of weight greater than ω. Hence, one can decide if there is a maximal matching in H with maximum weight ω and by using binary search, one can compute a maximal matching in H which minimizes the maximum weight, in time

O(log k((n + k) 2 log(n + k) + k(n + k) min(n, k))).
Assuming k = O(n), the algorithm above has a complexity of O(n 3 ). When the number of agents k is considerably smaller than n, the algorithm would only be faster.

We now present the approximation algorithms for FixedPath Collab-orativeDelivery in directed and undirected graphs, based on the above observations.

Directed graphs: 3-approximation

Theorem 3. There is a 3-approximation algorithm for FixedPath Collabo-rativeDelivery on directed graphs.

Proof Consider an instance (G, w, P, p 1 , . . . , p k ) of FixedPath Collabo-rativeDelivery on directed graphs and let S be an optimal solution of this instance with uniform budget B. Let l = w(P )/B . Case(i): If B ≥ w(P ), then any agent that can reach s can transport the package to t using an additional budget of B. Since there must exist such an agent and it is possible to find such an agent in O(k) time by a linear search over all agents, this give us the required approximation algorithm.

p 3i-2 p 3i p 3i-1 1/2 1/2 1/2 0 1/2
Figure 2: Illustration of the variable gadget for the case where agents cannot pickup the package more than once.

Lower bound

Theorem 5. The minimum uniform budget required to solve FixedPath Col-laborativeDelivery on directed graphs cannot be approximated to within a factor better than 1.5 in polynomial time, unless P = NP, even when each agent may pickup the package at most once.

Proof We use the same construction as in the proof of Theorem 1, but we set ε = 3/2 and q = 0 (cf. Fig. 2). All claims in the proof of Theorem 1 remain valid for any B < 3/2. Note that, since we eliminated all blockers, no agent has to pickup the package more than once in the optimum solution.

Approximation algorithm for single pickup per agent

We now present approximation algorithms for FixedPath Collabora-tiveDelivery with the restriction of a single pickup per agent. This means that for agents with uniform budget B, any two points on the fixed path P that are separated by a distance of at least B must be served by distinct agents. This observation allows us to match the agents to specific points on the path P (as opposed to intervals on the path in the general case considered in the previous section). The rest of the algorithm is based on similar ideas as in the previous section.

Lemma 3. Given any instance of FixedPath CollaborativeDelivery that admits a solution using optimal uniform budget B, under the restriction that each agent can pickup the package at most once; then given the value of B, we can compute in polynomial time a 2-approximate delivery strategy with a single pickup per agent. When the graph is undirected, we can compute a (2 -1/2 k )approximation for the same problem in polynomial time.

Proof Suppose there exists a feasible solution S for the problem using uniform budget B and a single pickup per agent. Consider the fixed (s, t) path P and partition it into segments using the points X = (m 1 , m 2 . . . m l = t) on P , such that l = w(P )/B and, the length of the first segment d P (s, m 1 ) ≤ B, the length of segment (m i , m i+1 ) is B, ∀1 ≤ i < l. We have the following observations for strategy S: (1) Any agent that moves the package over point m i ∈ X in strategy S must have enough energy to reach point m i , and (2) Any single agent cannot transport the package over two distinct points in X since the distance between these two points is at least B.

Case (i):

In strategy S, the agent that picks up the package at s is not the same agent that moves the package over m 1 . In this case, there exists a matching between the agents and the points X + = (s = m 0 , m 1 , m 2 , . . . m l ) such that each agent can reach the point that it is mapped to. We call any such matching a type M 0 matching. Case (ii): In strategy S, a single agent delivers the package from s to m 1 with its original energy budget B. In this case, there exists a matching between the agents and the points in X (w.l.o.g. agent a i is mapped to point m i ), such that, agent a 1 has enough energy to move the package from s to m 1 and ∀1 < i < l, agent a i can reach m i , using budget B. We call any such matching a type M 1 matching.

Note that if S is a feasible solution to the problem using a single pickup per agent and uniform budget B, then there exists a matching of type M 0 or M 1 . If we can find such a matching, then, using budget B per agent, we can move the package to point m 1 and move each agent a i to the respective point m i in path P . If the budget of each agent is augmented by factor 2, then using the additional budget B, the agent a i that is mapped to point m i can actually deliver the package to the next point m i+1 . This gives a 2-approximate solution to the problem (for directed and undirected graphs).

For undirected graphs, we will now construct a delivery strategy where each agent has a budget 2B -B/2 k . We consider the same two cases as before. Case (i): The delivery strategy S uses at least l + 1 agents and there is a a type M 0 matching between the agents and l + 1 points s = m 0 , m 1 , m 2 , . . . m l = t. Consider the points m i = m i + B -(2 i -1)B/2 l+1 , 0 ≤ i ≤ l -1. The agent a 0 can the package from point s = m 0 to m 0 using additional budget of B(1 -1/2 l+1 ). For 0 < i < l, each agent a i located at point m i returns to m i-1 to pick up the package and then moves the package to point m i . This requires an additional budget of B -(2 i -1)B/2 l+1 + 2 × 2 i B/2 l+1 = B(1 -1/2 l+1 ), for each of these agents. Finally, note that the distance between point m l-1 and the target t = m l is at most B/2 -B/2 l+1 , and so the agent a l can move from m l to m l-1 to pick up the package and deliver it to the target, using 2 × (B/2 -B/2 l+1 ) < B(1 -1/2 l+1 ) ≤ B(1 -1/2 k ) additional energy. Case (ii): The delivery strategy S uses l agents and there is a a type M 1 matching between the agents and l points s = m 1 , m 2 , . . . m l = t. Consider the points

m i = m i + B -(2 i -1)B/2 l , 1 ≤ i ≤ l -1.
The agent a 1 delivers the package from point m 1 to m 1 . For 1 < i < l, each agent a i located at point m i returns to m i-1 to pick up the package and then moves the package to point m i . This requires an additional budget of B -

(2 i -1)B/2 l + 2 × 2 i B/2 l = B(1 -1/2 l ),
for each of these agents. Finally, note that the distance between point m l-1 and the target t = m l is at most B/2 -B/2 l , and so the agent a l can move from m l to m l-1 to pick up the package and deliver it to the target, using

× (B/2 -B/2 l ) < B(1 -1/2 l ) ≤ B(1 -1/2 k ) additional energy. 2
The computation of the schedule requires constructing a bipartite graph between k agents and at most k points, and then solving maximum matching in this bipartite graph. Similar to the proof of Lemma 2, these computations can be performed in O(n 3 ) time.

As in the previous section, we use a binary search to find the smallest B for which there exists a matching of type M 0 or M 1 from the above lemma. This gives us a (2 -1/2 k )-approximate (respectively 2-approximate) solution to the optimization problem for undirected (resp. directed) graphs. Hence we can state the following theorem: Theorem 6. The minimum uniform budget required to solve FixedPath Col-laborativeDelivery with a single pickup per agent on directed (and undirected) graphs can be approximated to a factor 2 (respectively (2 -1/2 k )), in polynomial time.

Fixed Path Delivery with O(1) agents

In this section we consider the FixedPath CollaborativeDelivery problem with only a few agents, i.e., when k is a small constant. Further we will assume in this section that the agents are allowed to exchange the package at vertices only. Recall that if there is a single agent (k = 1) then the problem can be solved trivially (by simply computing the shortest path from the agent to the source). However for k > 1 agents, the problem is weakly NP-hard. Theorem 7. FixedPath CollaborativeDelivery is (weakly) NP-hard for k = 2 agents even if the agents are restricted to pickup the package only at vertices of G.

Proof Consider a complete graph on n vertices where the fixed path P is (s = v 1 , v 2 , v 3 . . . v n = t), k = 2 and both the agents are initially located at the source. We show a reduction from the NP-complete problem Subset-Sum: Given a set X of n integers a 1 , a 2 , . . . a n whose sum is 2S, does there exist a subset of X whose sum is exactly S?

We construct the instance of FixedPath CollaborativeDelivery by assigning weights a 1 , a 2 , . . . , a n to the edges (v 1 , v 2 ), (v 2 , v 3 ), . . . (v n-1 , v n ) of the path P and we assign weight zero to all other edges of the complete graph. Finally we assign a budget of B = S to each agent. It is easy to see that there is a feasible delivery schedule by the two agents if and only if each agent can move on a subset of edges whose sum of weights equals S, which is equivalent to finding a subset of sum S for the instance of subset sum.

Given an instance of the decision problem for a specific B, we can design a dynamic programming algorithm that computes whether there exists a feasible schedule with uniform budget B, and has a running time that is exponential in k and pseudo-polynomial in n (the run-time will depend on B). Theorem 8. There is an algorithm that decides whether there exists a feasible schedule restricted to pickup at vertices, for FixedPath CollaborativeDelivery with uniform budget B in undirected or directed graphs. The algorithm runs in O(k • n k+2 • B k ) time. modified edge-weights. Hence, B = max i { w( Pi )}, and thus B • µ = max i { w( Pi ) • µ}. Observe also that B A is a feasible budget, since every path Pi can be walked with budget B A , since the original length of Pi is w( Pi ) ≤ µ • w( Pi ) ≤ µ B.

Let B * be the optimum budget for the original edge-weights, and let P * 1 , . . . , P * k be the walks of the k agents in some optimum solution. Hence, B * = max i {w(P i )}.

We now argue that B A is not much larger than B * . We have

B A = µ • B = µ•max i { w( Pi )} (1)
≤ µ•max i { w(P * i )} = max i {µ• w(P * i )}

≤ max i {w(P * i )+m 2 µ} = m 2 µ + max i {w(P * i )} = m 2 µ + B * = m 2 w(P )/k+X

m 2 + B * (3)
≤ • B * + B * = (1+ )B * . Here, inequality (1) is because max i Pi is the optimum feasible solution in weights w; inequality (2) follows because any walk appears at most m times on the path P , and between any two appearances, the walk contains at most m edges (this part of the walk is a simple path), inequality (3) follows because B * needs to be at least w(P )/k + X (the average traveled distance per agent on P plus the distance to get from the initial position to the path P ).

We now analyze the run-time of the algorithm. Observe first that B * ≤ min i d(p i , s) + w(P ) ≤ (X + w(P )) + w(P ) ≤ 2(X + w(P )). Therefore, measured in the units µ, we search for B in the range between 1 and 2(X +w(P ))/µ ≤ 2m 2 k . Hence, one run of the dynamic programming on the modified weights takes time O(k • n k+2 • ( 2m 2 k ) k ). Using the binary search to find the minimum such B adds a multiplicative logarithmic factor of log 2m 2 k . This proves the theorem. Thus, we have shown the following.

Corollary 1. There exists an FPTAS for FixedPath CollaborativeDelivery restricted to pickup at vertices, when the number of agents is constant.

Conclusions

The problem of collectively delivering a package by mobile agents is a difficult problem even when the path for moving the package is given in advance. We presented approximation algorithms and lower bounds of approximation for the fixed path version of the problem. These results leave some gaps and we would like to reduce the gap between the upper and lower bounds for the various versions of the problem. We also considered the special case of fixed path delivery with a single pickup per agent, and we were able to find better approximation algorithms for this case compared to the best known algorithm for collaborative delivery without fixed path. This seems to suggest that the fixed path version admits better approximation than the general version, when each agent is restricted to a single pickup. However to prove this we need to find lower bounds on the approximation factor of collaborative delivery. Another possible extension to this work is to consider agents with non-uniform budgets and find resource-augmented algorithms for fixed path delivery. Finally, we would like to analyse more precisely the effect of restricting package handovers to nodes only and not anywhere inside the edges.

Figure 1 :

 1 Figure 1: Illustration of the variable gadget. The horizontal arcs are part of the fixed path of the package. Colors indicate responsibilities: blue nodes are for blockers and green/red nodes contain agents associated with positive/negative literals.

$ This work was partially supported by the ANR project ANCOR (anr-14-CE36-0002-01). The third author was supported by the 'Excellence Initiative' of the German Federal and State Governments and the Graduate School CE at TU Darmstadt.

Case(ii): If B < w(P ) then l = w(P )/B ≥ 2. Thus we can apply the Lemma 1 using points m 0 = s, and m i = s + i • B, 0 < i < l on the path P . Note that the last point satisfies the property 0 < d P (m l-1 , t) ≤ B. Let a 0 , . . . a l-1 be the matching agents according to Lemma 1 (which can be computed using the algorithm from Lemma 2). Since agent a 0 can reach the source s = m 0 using budget B, it can transport the package to point m 1 using a budget of at most 2B in total. For 0 < i < l -1, agent a i can reach the point m i using a budget of at most 2B and thus it can transport the package from m i to m i+1 using a budget of at most 3B in total. Similarly, the agent a l-1 can transport the package from m l-1 to the target t. This gives the required 3-approximation.

Undirected graphs: 2.5-approximation

Theorem 4. There is a 2.5-approximation algorithm for FixedPath Collab-orativeDelivery on undirected graphs.

Proof Consider an instance (G, w, P, p 1 , . . . , p k ) of FixedPath Collab-orativeDelivery on undirected graphs and let S be an optimal solution of this instance with uniform budget B. If w(P ) ≤ 3B/2, then any agent that reaches the vertex s can carry the package to t, using an additional budget of 3B/2, and this immediately gives a 2.5-approximation. Thus, let us assume that w(P ) > 3B/2 and consider l = w(P )/B -1/2 ≥ 2.

We define the points m 1 , . . . m l on P such that m i + (l -i) * B = t, for 1 ≤ i ≤ l (thus m l = t). Note that the distance from s to m 1 is at most 3B/2. Now let m i be the point on path P defined as m i = m i+1 -B/2 for 0 ≤ i < l. Thus the point m i is the midpoint between m i-1 and m i for 1 < i ≤ l and the point m 0 is at a distance at most B from s. Now we can apply Lemma 1 using points s, m 0 , . . . m l-1 to obtain matching agents a 0 to a l-1 . Agent a 0 can reach the source s and thus it can transport the package to m 1 using an additional budget of 3B/2. Agent a i , 0 < i < l can reach the interval (m i-1 , m i ), and thus using an additional budget B/2, the agent can reach the mid-point m i (this may involve going back on the path). Thus agent a i can transport the package from m i to m i+1 using a total budget of at most 2.5 * B which gives the required approximation algorithm.

Special case: Single pickup per agent

In this section, we consider a slightly easier version of the problem when each agent can pickup the package at most once. This means that each agent that participates in the solution, moves the package over a single continuous segment of the path. In this case, we can obtain better approximations for the problem. We first present a lower bound of 3 2 on the approximation ratio of optimizing FixedPath CollaborativeDelivery using the same idea as in Section 2.

Proof The algorithm works as follows. We keep a boolean table whose entries are of the form

denoting whether there exists a feasible schedule that delivers the package from s to vertex v on the path P such that 1. the last agent that delivers the package to vertex v is agent a j , 2. the positions of the k agents, when the package arrives at v, are p v 1 , . . . , p v k , and 3. the remaining budgets of the agents are B v 1 , . . . , B v k . We initialize T s [0|p 1 , . . . , p k |B, . . . , B] = TRUE and initialize T s [...] = FALSE for all other values of j and p s i and B s i , i = 1, . . . , k. Here, j = 0 denotes that no agent has been used yet. We also abuse the notation and use p 0 to denote s.

and there exists a vertex u on the path P before vertex v and an agent's index j = j such that there is a feasible schedule where agent a j walks from position p u j to pick-up the package at vertex u from agent a j and carries it from vertex u to vertex v. I.e., we have

= TRUE if and only if there exists u and j and an entry in the table

Recall that d P (u, v) denotes the distance from u to v on the path P .

At the end, when the whole table is computed, we check whether there is an entry at target vertex t such that T t [. . .] = TRUE, in which case there is a feasible schedule for the uniform budget B, and there is no feasible schedule otherwise. To compute the feasible schedule, standard bookkeeping techniques can be applied. There are n • n k • B k entries in T that need to be computed. To compute one entry T v [j|p v 1 , . . . , p v k |B v 1 , . . . , B v k ], we need to check the existence of j and u with the above mentioned properties, which can be done in time O(k • n). Hence, the total run-time of the alorithm is

By using the data rounding technique, we turn the developed algorithm into a fully polynomial-time approximation scheme (FPTAS). Theorem 9. For any > 0, there is an algorithm that computes a feasible uniform budget B that is at most (1 + )B * , where B * is the optimum uniform budget, and runs in O k

Proof We define an alternative weight unit µ := w(P )/k+X m 2

, where w(P ) is the weight of the fixed path P , X is the minimum distance of any agent to the path P , and m is the number of edges of the graph G. We measure the weights w(e) in the integer multiples of µ, rounded-up, i.e., we define w(e) := w(e)/µ .

We solve the problem in the new edge weights w(e) using the dynamic programming approach, where we also measure budget in multiples of µ. Let B be the computed optimum uniform budget for the modified edge-weights. Our algorithm returns B A = B • µ as the solution for the original edge-weights. Let P1 , . . . , Pk be the walks that the k agents walk in the optimum solution for the