Andreas Bärtschi
email: baertschi@lanl.gov

Evangelos Bampas

Jérémie Chalopin

Shantanu Das

Christina Karousatou

Matúš Mihalák

Near-gathering of energy-constrained mobile agents

Keywords: mobile agents, power-aware robots, limited battery, gathering, graph algorithms, approximation, computational complexity

published or not. The documents may come

Introduction

The problem of gathering is one of the fundamental problems in distributed computing with mobile entities, which includes mobile agents moving in a graph or robots moving in a continuous geometric space. In both cases, the objective is to bring together multiple autonomous agents to a single point (not predetermined). Gathering helps in coordination between the mobile agents, sharing of information between the entities, reassignment of duties among the entities, and even for protection of the agents (a group of robots gathered together is easier to protect than those dispersed in a large area). Moreover, there are also theoretical reasons for studying gathering, as the problem of selecting a gathering point is akin to problems of leader election and consensus in distributed systems. However, in some cases, it may be impossible to solve the problem of gathering, e.g. due to limitations in the capabilities of the agents, or due to symmetries in their perception of the environment. In some cases it may be desirable for the agents to get close to each other without actually meeting [START_REF] Pagli | Getting close without touching: Near-gathering for autonomous mobile robots[END_REF].

In this paper, we consider mobile agents moving on a graph, with severe limitations on their movements. We assume that the agents have limited energy resources and traversing any edge of the graph consumes some of this energy which can not be replenished. In other words, each agent has an initial energy budget which limits the total distance it can move in the graph. Under such constraints, it is not always possible to gather the agents at a single point. Thus, we consider the problem of moving the agents as close as possible to each other while respecting the movement constraints, defined below as the near-gathering problem.

Near-Gathering. A collection of k mobile agents is initially located at an arbitrary set of nodes of an undirected edge-weighted graph G = (V, E, ω).

Each agent i, i = 1, . . . , k, has an energy capacity b i , which represents the maximum distance the agent can move in the graph. The agents have global knowledge of the graph and are controlled by a central entity. The goal is to move the agents to a configuration where they are as close to each other as possible under their respective limitations of movement. Closeness criteria can be measured, e.g., as the size of the smallest region enclosing all the agents, or as the maximum or average pairwise distance between the agents.

We look at each of these criteria and give a more precise definition of the problem below.

Our Model. We consider an undirected graph G = (V, E, ω), where each edge e ∈ E has a positive weight ω(e) > 0. As usual, the length of a path is the sum of the weights of its edges. We think of every edge e = {u, v} as a segment of infinitely many points, where every point in the edge is uniquely characterized by its distance from u, which is between 0 and w(e).

We consider every such point to subdivide the edge {u, v} into two edges of lengths proportional to the position of the point on the edge. Thus, the distance d(p, q) between two points p and q (nodes or points inside edges) is the length of a shortest path from p to q in G (with edges subdivided by p, q, respectively). For a point p inside an edge e ∈ E we write p ∈ G and p ∈ seg(e).

A collection of k mobile agents is initially located at an arbitrary set of nodes p 1 , . . . , p k ∈ V . Each agent i is equipped with an energy budget b i > 0 and can move along edges of the graph, for a distance of at most b i . In the Near-Gathering problem, the goal is to relocate every agent into a new position such that the resulting configuration minimizes one of the following objectives: (i) the radius of a smallest ball containing all agents, (ii) the maximum distance between any two agents, or (iii) the average distance between the agents (or, equivalently, the sum of all distances). We are further interested in two variants of the problem, where agents can: (I) only be relocated to reachable nodes of the graph, or (II) in a more general scenario, where the agents are allowed to be relocated to reachable points (i.e., nodes or points inside edges).

Definition 1 (Near-Gathering).

Instance: G, k, (p i ) i=1,...,k , (b i ) i=1,...,k , where G = (V, E, ω) is an undirected edge-weighted graph, k denotes the total number of agents, p i denotes the initial position of agent i and b i denotes the total amount of energy agent i initially has at its disposal. We consider both the scenario with node centers only, and the scenario with arbitrary point centers.

(ii) MinDiam: Minimize Diam(C), where Diam(C) = max i,j d(c i , c j ).

(iii) MinSum: Minimize Sum(C), where Sum(C) = i j d(c i , c j ).

Related Work. The gathering problem has been studied in two very different scenarios (i) Gathering of mobile agents in a connected (finite or infinite) graph, and (ii) Gathering of mobile robots in a (bounded or unbounded) plane or other geometric spaces. In the context of distributed robotics or swarm robotics [START_REF] Flocchini | Distributed Computing by Mobile Entities[END_REF], the problem of gathering many robots at a single point has been studied as an agreement problem, where the main issue is feasibility of gathering starting from arbitrary configurations [START_REF] Cieliebak | Distributed computing by mobile robots: Gathering[END_REF] or gathering without full knowledge of the configuration [START_REF] Flocchini | Gathering of asynchronous robots with limited visibility[END_REF][START_REF] Lin | The multi-agent rendezvous problem. parts 1 and 2[END_REF]. The problem of convergence requires the robots to converge towards a point [START_REF] Cohen | Convergence properties of the gravitational algorithm in asynchronous robot systems[END_REF], without actually arriving at the gathering point. When the robots are not allowed to collide, the problem of moving the robots closer avoiding any collisions has been studied by Pagli et al. [START_REF] Pagli | Getting close without touching: Near-gathering for autonomous mobile robots[END_REF]. In all these studies, the robots can move freely in any direction.

For mobile agents on the graph that are restricted to move along the edges, gathering has been studied under different models (see e.g. [START_REF] Czyzowicz | How to meet asynchronously (almost) everywhere[END_REF][START_REF] Pelc | Deterministic rendezvous in networks: A comprehensive survey[END_REF]). In particular, the gathering of two agents, often called rendezvous, has attracted a lot of attention, well documented in [START_REF] Alpern | The Theory of Search Games and Rendezvous[END_REF]. The problem of gathering with the objective of minimizing movements has been studied in [START_REF] Cicerone | Gathering of robots on meetingpoints: feasibility and optimal resolution algorithms[END_REF]. However to the best of our knowledge, there have been no previous studies on gathering with fixed constraints (budgets) on energy required for movements.

The model of energy-constrained agents was introduced in [START_REF] Betke | Piecemeal learning of an unknown environment[END_REF][START_REF] Awerbuch | Piecemeal graph exploration by a mobile robot[END_REF] for single agent exploration of graphs. Duncan et al. [START_REF] Duncan | Optimal Constrained Graph Exploration[END_REF] consider a similar model where the agent is tied with a rope of length b to the starting location. Multi-agent exploration under uniform energy constraint of b has been studied for trees [START_REF] Fraigniaud | Collective tree exploration[END_REF][START_REF] Dynia | Power-Aware Collective Tree Exploration[END_REF] with the objective of minimizing the energy budget per agent [START_REF] Dynia | Why robots need maps[END_REF] or the number k of agents [START_REF] Das | Collaborative Exploration by Energy-Constrained Mobile Robots[END_REF] required for exploration, while time optimal exploration was studied by Dereniowski et al. [START_REF] Dereniowski | Fast collaborative graph exploration[END_REF] under the same model. Demaine et al. [START_REF] Demaine | Minimizing movement[END_REF][START_REF] Demaine | Minimizing movement: Fixedparameter tractability[END_REF] studied problems of optimizing the total or maximum energy consumption of the agents when the agents need to place themselves in desired configurations (e.g. connected or independent configurations); they provided approximation algorithms and inapproximability results. Similar problems have been studied for agents moving in the visibility graphs of simple polygons [START_REF] Bilò | Polygon-Constrained Motion Planning Problems[END_REF].

For the model studied in this paper, where each agent has a distinct energy budget, the problem of Broadcast and Convergecast was studied in [START_REF] Anaya | Convergecast and Broadcast by Power-Aware Mobile Agents[END_REF] who provided hardness results for trees and approximation algorithms for arbitrary graphs. The problem of delivering packages by multiple agents having energy constraints was studied in [START_REF] Chalopin | Data Delivery by Energy-Constrained Mobile Agents[END_REF][START_REF] Chalopin | Data Delivery by Energy-Constrained Mobile Agents on a Line[END_REF][START_REF] Bärtschi | Collaborative Delivery with Energy-Constrained Mobile Robots[END_REF][START_REF] Bärtschi | Collaborative delivery with energyconstrained mobile robots, Theoretical Computer ScienceTo appear[END_REF]. All of these problems were shown to be NP-hard for general graphs even if the agents are allowed to exchange energy when they meet [START_REF] Czyzowicz | Communication Problems for Mobile Agents Exchanging Energy[END_REF][START_REF] Bampas | Collaborative delivery by energy-sharing low-power mobile robots[END_REF].

Our Contribution and Paper Organization. In Section 2, we establish a few preliminaries and prove that MinBall is solvable in polynomial-time. In Section 3 we give a 2-approximation algorithm for MinDiam, together with a matching NP-hardness lower bound; additionally we show that MinDiam is polynomial-time solvable on tree graphs. In Section 4, we prove that MinSum admits a 2(1 -1 k )-approximation algorithm but no FPTAS, unless P = NP. We show that the analysis of the approximation ratio of the provided algorithm is tight.

We conclude with remarks on future research opportunities, including preliminary approximation hardness results for additive approximation of MinDiam, in Section 5. All our results -with the exception of additive approximation -hold for both node-stop as well as arbitrary-stop scenarios.

Preliminaries and Minimizing the Radius

Preliminaries. We first point out some differences in the two scenarios we consider throughout this paper and our general approach on how to tackle and distinguish those. In the node stop scenario, where each agent i is only allowed to move to nodes v with distance d(p i , v) ≤ b i , there is a finite number of feasible configurations C. For the scenario with arbitrary final positions, where agents are also allowed to move to points p inside edges (as long as d(p i , p) ≤ b i ), we discretize the set of configurations. In the MinBall variant of Near-Gathering, the discretization turns out to contain at least one optimum solution, for MinDiam and MinSum it will at least contain a configuration approximating an optimum solution within a factor of 2 or 2(1 -1 k ), respectively. To this end, we define sets of reachable nodes and "maximally reachable" in-edge points as follows:

Definition 2 (Balls, Spheres). For an instance G, k, (p i ) i=1,...,k , (b i ) i=1,...,k with initial agent positions p i and energy budgets b i , we define

• B(i) := {v ∈ V | d(p i , v) ≤ b i }, i.e.
the ball containing all nodes that agent i can reach from its initial position p i , and

• S(i) := ∅ for node stops, and S(i

) := {p ∈ G | d(p i , p) = b i } \ B(i) for
arbitrary stops, i.e. the sphere of all in-edge points that agent i can reach from its initial position p i only by spending its whole budget b i .

In the same spirit, we can study MinBall-Gathering for centers c being restricted to nodes in V , or for the continuous set of center points being allowed to be placed both on nodes as well as the inside of edges of G. To discretize this set, it will be useful to define a set of midpoints, intuitively consisting of "points m lying in the middle of a trail between points p and q": Definition 3 (Midpoints). Given a set S of points in G, denote by G = (V , E , ω ) the graph we get from G = (V, E, ω) by subdividing the edges in E with points from S, i.e. V = V ∪ S. We define the midpoint set M (S) of points in G -and by bijection also of G -as: In order to compute the set M (S) of midpoints of a given set S of points in G, we first compute shortest-paths trees for all points p ∈ S to all nodes

M (S) := {m ∈ V | ∃ p, q ∈ S : d(p, m) = d(m, q)} ∪ {m ∈ seg(e) | e = {u, v} ∈ E , ∃ p, q ∈ S : d(p, u) + d(u, m) = d(m, v) + d(v, q)} .
v ∈ V in time O(|S| • |V | 2 ) ⊆ O(|S| 3 + |S| • |V | 2 ).
Then we check for each node v ∈ V whether it is contained in M (S) by iterating over all pairs of points p, q ∈ S. Similarly, we check for each edge e = {u, v} ∈ E and all pairs of points p, q ∈ S in constant time (having already computed the distances d(p, u), d(p, v), d(q, u) and d(q, v)) whether and where there are any (at most 2) midpoints m ∈ seg(e) of p and q. Overall,

M (S) is of size O(|S| 2 • |V | 2 ) ⊆ O(|S| 4 + |S| 2 • |V | 2
) and can be computed in time

O(|S| 4 + |S| 2 • |V | 2 ) as well.
MinBall for node centers. Having defined balls and spheres of reachable points for the agents, we can immediately give an exhaustive search algorithm for MinBall for centers restricted to nodes. The main idea of Algorithm 1 is to fix a node in graph G as a gathering point and then for each

Algorithm 1 MinBall (node centers) Input: An instance G, k, (p i ) i=1,...,k , (b i ) i=1,...,k . Output: Configuration C, center c ∈ V with minimum radius Radius(C, c). 1: for each v ∈ V do 2: Compute C v := (c v 1 , . . . , c v k ), 3:
where

c v i ∈ arg min{d(v, c i ) | c i ∈ B(i) ∪ S(i)} is a point in 4:
B(i) ∪ S(i) minimizing the distance to v, breaking ties arbitrarily.

5:

Compute Radius(C v , v). 6: end for 7: Return arg min

C v , v : v∈V Radius(C v , v).
agent i compute the minimum distance to this fixed center it can reach, given its starting position p i and its energy budget b i . Iterating over all possible center nodes, we find an optimal solution: MinBall for arbitrary centers. We now extend our approach to find optimum MinBall solutions for arbitrary centers. As can be seen from Lemma 2, when testing for a fixed center c, in addition to checking the points in B(i) ∪ S(i) we should also consider whether agent i can reach c itself. As candidates for the center c we take all points in the midpoint set M (V ∪ i S(i)), yielding Algorithm 2:

Theorem 2 (MinBall, arbitrary centers). Algorithm 2 is a polynomial-time algorithm for MinBall with arbitrary centers.

As before, polynomial running time follows from the polynomial size of the candidate set M (V ∪ i S(i)). Building upon Algorithm 1 and Theorem 1, it remains to show that this set contains an optimum center:

Lemma 3.
There exists an optimum solution (O, o) for MinBall where

the center o is contained in M (V ∪ i S(i)). Proof. Given any optimum configuration C = (c 1 , . . . , c k ) with center c / ∈ M (V ∪ i S(i)
) and agent stopping positions c i adhering to Lemma 2, we can

directly construct an optimum solution (O, o) for which o ∈ M (V ∪ i S(i)).
Let G = (V , E , ω ) be the graph we get from G = (V, E, ω) by subdividing the edges in E with points from i S(i). c).

1: for each p ∈ M (V ∪ i S(i)) do 2:
Compute C p := (c p 1 , . . . , c p k ),

3:

where either

c p i = p if d(p i , p) ≤ b i , or otherwise 4: c p i ∈ arg min{d(p, c i ) | c i ∈ B(i) ∪ S(i)}
(breaking ties arbitrarily).

5:

Compute Radius(C p , p). 6: end for 7: Return arg min

C p , p : p∈M (V ∪ i S(i))
Radius(C p , p).

Minimizing the Diameter

In this Section, we prove that Algorithm 2, which computes an optimum solution for MinBall, also computes a 2-approximation for MinDiam. As we will show, this is likely best-possible, as there is no polynomial-time (2o(1))-approximation for MinDiam, unless P = NP. Nonetheless, for the special case of tree graphs, Algorithm 2 even computes an optimum solution for MinDiam. We start with the positive results: (even though o might not have been considered as a center candidate, see e.g. Figure 1 (left)). Combining all inequalities, we get

points c * i , c * j that d(c * i , c * j ) ≤ d(c * i , c * ) + d(c * j , c * ) and thus d * ≤ 2 • r * . p 2 b 2 =6 p 1 b 1 =6 o 1 p 3 b 3 =6 S(3) o 3 o 2 S (2)
d * ≤ 2 • r * ≤ 2 • r o ≤ 2 • d Opt , hence C * is a 2-approximation for MinDiam.
Theorem 4 (MinDiam, on Trees). Algorithm 2 is a polynomial-time algorithm for MinDiam on trees.

Proof. First note that if there is a configuration O with maximum distance Diam(O) = 0, it also has radius Radius(O, o) = 0 for some center o, and thus will be found by Algorithm 2 as proven in Theorem 2. Otherwise the diameter Diam(O) of an optimum solution O is lower bounded by the largest diameter among all optimal solutions of the instance reduced to pairs of agents i, j:

d * :=    max i,j min q i ∈B(i), q j ∈B(j)
d(q i , q j ) for the node stop scenario, Since we consider tree graphs here, there is a unique shortest path from q a to q b and thus a unique midpoint

c * ∈ G with d(c * , q a ) = d(c * , q b ) := d * 2 .
As c * is contained in M (V ∪ i S(i)), Algorithm 2 will use c * as a center point candidate for which it computes a configuration

C * = (c * 1 , . . . , c * k ). By definition, we have d(c * , c * a ) = d(c * , q a ) = d * 2 = d(c * , q b ) = d(c * , c * b ).
It is enough to show that for all other agents i we have

d(c * , c * i ) ≤ d * 2 ,
too. Assume for the sake of contradiction that this is not the case and that there is an agent i with x n is satisfied by Agents & reduction idea: On each of the nodes in V x ∪ V C we place one agent with a budget of b = 1, for a total of n + m agents. The main idea is to initially space the agents by a pairwise distance of 3. We then let agents on V x "pick the value assignment of the variables x i " by walking to their respective node in V , whereas we let agents on V C "pick the truth assignment of the clauses C j " by walking to their respective node in V L . Then a satisfiable assignment of φ exists, if and only if the variable agents and the clause agents "agree in their choice" which corresponds to an optimum MinDiam configuration O of diameter 1. Furthermore, any other configuration should have diameter ≥ 2. This gives rise to the

d(c * , c * i ) > d * 2 .
x 1 , x 2 , x n ∈ L \ {F F T }). Now, let V := V x ∪ V ∪ V C ∪ V L , where • V x = {v i | 1 ≤ i ≤ n} are nodes corresponding to variables x 1 , . . . , x n , • V = {v T i | 1 ≤ i ≤ n} ∪ {v F i | 1 ≤ i ≤ n}

Set of edges

E := E x ∪ E L ∪ E CL ∪ E ∪ E LL , where: • E x = {{v i , v T i }, {v i , v F i } | 1 ≤ i ≤ n : v i ∈ V x , v T i , v F i ∈ V } are edges
connecting each variable node x i to its two literal nodes, . . . are not connected to nodes c 1 and c m , respectively. The location of mobile agents is denoted by squares ( ).

C 1 = (x 1 ∨ x 2 ∨ x n ) c 1 C m = (x 1 ∨ x 2 ∨ x 3 ) c m 2n-clique 8m-clique . . . . . . . . . c TTT m c TTF m c TFT m c TFF m c FTT m c FTF m c FFT m c FFF m c TTT 1 c TTF 1 c TFT 1 c TFF 1 c FTT 1 c FTF 1 c FFT 1 c FFF m x 1 v 1 x 2 v 2 x n v n v T 1 v F 1 v T 2 v F 2 v T n v F n V x V V L V C E x E E L E LL E CL
• E CL = {{c j , c l j } | 1 ≤ j ≤ m : c j ∈ V C , c l j ∈ V L , c l j satisfies C j }
are edges connecting each clause node c j with all nodes representing satisfying assignments for clause C j ,

• E L = {{v i , c l j } | i ≤ n, j ≤ m : v i ∈ {v T i , v F i } ⊂ V , c l j ∈ V L , such that either x i does not appear in C j ,
or x i appears in C j and v i agrees with c l j } are edges connecting unrelated literals and clause truth-assignments, as well as matching literals and clause truth-assignments.

• E = {{u, v} | u, v ∈ V } and E LL = {{u, v} | u, v ∈ V L } are edges
pairwise connecting nodes in V , and nodes in V L , respectively.

Figure 2 shows a part of an instance of MinDiam which is constructed from an instance of 3Sat as described above. Before giving a proof of Theorem 5, we argue that no agent would stop in the middle of an edge:

c i ∈ V ∪ V L . v 1 v T 1 v F 1 2n-clique δ b -δ 1 b
Figure 3: A configuration C where agent a(v 1 ), depicted by , stops at distance δ from its starting node v 1 : Moving fully to v F 1 will only decrease the diameter Diam(C).

Proof. Consider an agent a(v i ) which corresponds to the variable x i and without loss of generality suppose that a(v i ) chooses to move towards node v F i . Assume now, for the sake of contradiction, that agent a(v i ) has stopped

at distance 0 ≤ δ < b = 1 on the edge (v i , v F i ), subdividing the edge into two segments (v i + δ, v i ) and (v i + δ, v F i ). (With δ = 0 indicating that a(v i )
stayed on v i without moving at all). In this case, a(v i ) has spent δ units of energy and has b -δ units of energy remaining (see Figure 3). Agent a(v i ) is connected with the rest of the agents through two possible paths: The first one is through the segment

(v i + δ, v F i ) of length b -δ > 0, the other one is through the path (v i + δ, v i ), (v i , v T i ) of length δ + b ≥ 1.
It is easy now to notice that if a(v i ) moves to node v F i (recall that it has b -δ units of energy remaining to do so), its distance to the other agents can only be reduced, as the contribution of the distance through v F i is now 0 and the contribution through node v T i is now 1. The same argument holds for the agents that correspond to the clauses. Hence moving all agents completely down to V , V L results in a configuration of non-increased diameter.

Proof. (Theorem 5). Based on the preceding construction of MinDiam instances from 3Sat instances and the structural Lemma 4, we now give a proof of Theorem 5.

⇒ We first show that if φ is satisfiable then there exists a configuration C of diameter Diam(C) = 1. Since φ is satisfiable we have a truth assignment to the variables which satisfies every clause of φ. For each variable x i , we let agent a(v i ) move to node v T i if x i = true and to node v F i otherwise. Next, for each clause C j , we let agent a(c j ) move to the node c l i , which corresponds to the correct true/false-assignment picked by the three agents of the variables in C j . Note that both types of moves can be done with an energy of b = 1.

Let us examine the maximum distance of any two agents in this final configuration. Notice that all agents {a(v i ) | v i ∈ V x } moved to nodes in V . By construction, they are pairwise connected with an edge in E . Similarly, the agents {a(c j ) | c j ∈ V C } have moved to nodes in V L and are thus connected by edges belonging to E LL . It remains to compute the distance between the variable agents (located in V ) and the clause agents (in V L ). Each agent a(c j ) by construction has distance equal to 1 from the three agents on nodes that correspond to the truth assignment of the variables contained in clause C j , namely through an edge of E L . Moreover, each agent a(c j ) has distance 1 from the nodes that belong to V which correspond to the truth assignment to variables that are not contained in clause c j . Therefore, the maximum distance between any two agents is equal to 1.

⇐ We now show that if φ is not satisfiable then every solution to Min-Diam is of size greater than or equal to 2. According to Lemma 4, we may assume without loss of generality that no agent stops inside an edge nor stays on its starting position. If φ is not satisfiable, then for every possible truth assignment to the variables, there exists at least one clause in φ that is not satisfied. Let us note here that in any optimum solution to MinDiam, the final positions of the agents that are initially located in variable nodes corresponds to a truth assignment to the variables. Therefore, any final configuration will correspond to a truth assignment to the variables which will not satisfy φ. Consider now an arbitrary final configuration of an instance of MinDiam. For the corresponding truth assignment to the variables, let us assume that the clause that is not satisfied is C y = (x r ∨ x s ∨ x t ). We can show that similar arguments hold for any unsatisfied clause (irrespective of whether the literals in the clause are positive or negative). If C y is not satisfied, this implies that agents a(v r ), a(v s ) and a(v t ) are located in nodes

v F r , v T s and v F t , respectively.
Let us examine the maximum distance of any two agents in this final configuration. Recall that the set of edges E CL connects each clause node to nodes corresponding to all possible satisfying assignments for this clause. As a result, nodes c y and c FTF Since a polynomial-time (2-o(1))-approximation algorithm for MinDiam could distinguish between instances with an optimum solution with diameter 1 and instances with an optimum solution with diameter 2, it would also be able to decide whether φ is satisfiable of not.

Minimizing the Average Distance

In this Section we describe and analyze an algorithm for minimizing the average pairwise distance between agents. We complement its approximation ratio of 2(1 -1 k ) with a tight analysis and rule out an FPTAS for MinSum.

The main idea of the presented Algorithm 3 for MinSum is similar to the idea of Algorithm 2 for MinDiam. We fix a point p in the graph G as a gathering point and move each agent i as close as possible to p with respect to its energy constraint, breaking ties arbitrarily. Algorithm 3 exhaustively tests all points in V ∪ i S(i) as possible gathering points and selects the point p with a configuration C = (c 1 , . . . , c k ) of minimum sum of pairwise distances between the agents, Sum(C) = i j d(c i , c j ). The choice of the search space for gathering points is based on a characterization of optimum solutions, similar in look and proof to Lemmata 2 and 3:

Lemma 5. There exists an optimum solution O for MinSum where every agent stops on a point in V ∪ i S(i).

Proof. Assume for the sake of contradiction that in every optimum configuration C = (c 1 , . . . , c j ), there is at least one agent j which stops on a point

c j / ∈ V ∪ i S(i).
Define by O the set of all optimum solutions, and with O ⊆ O its subset of configurations with a minimum number of agents j

such that c j / ∈ V ∪ i S(i). We denote by C * = (c * 1 , c * 2 , . . . c * k ) a configu-
ration with a maximum number of agents stopping on any common point • The pairwise distances in A = , in A u , and in A v individually and the distances between agents in A u and agents in A v stay the same.

c * / ∈ V ∪ i S(i),
• The distances between agents in A = and in A u decrease by ε each.

• The distances between agents in A = and in A v increase by at most ε.

Overall, Sum(C * ) changes under the moving operation by a total value of at most 2ε

• |A = | • |A v | -2ε • |A = | • |A u | ≤ 0.
j ) = 1 k • k j d(o, o j ) ≤ 1 k • i j d(o i , o j ) = 1 k • s Opt . ( 1
)
Algorithm 3 MinSum (2(1 -1 k )-apx) Input: An instance G, k, (p i ) i=1,...,k , (b i ) i=1,...,k . Output: Configuration C with Sum(C) ≤ 2(1 -1 k ) • min feasible C Sum(C ). 1: for each p ∈ V ∪ i S(i)
c p i ∈ arg min{d(p, c i ) | c i ∈ B(i) ∪ S(i)}
(breaking ties arbitrarily).

5:

Compute Sum(C p ).

s * ≤ s o = i j d(c o i , c o j ) ≤ 2 j d(c o a , c o j ) + i =a j =a j =i (d(c o i , o) + d(o, c o j )) = 2 j d(o, c o j ) + (k -2) i =a d(c o i , o) + (k -2) j =a d(o, c o j ) = (2k -2) j d(o, c o j ) ≤ 2(k -1) j d(o, o j ) (1) ≤ 2(1 -1 k ) • s Opt .
(Lower bound). To see that the above analysis is tight, we construct instances G, k, (p i ) i=1,...,k , (b) i=1,...,k with k agents of uniform budget b = 1, for which the tie-breaking in Line 3 of Algorithm 3 leads to a configuration

C with Sum(C) = 2(1 -1 k ) • Sum(O).
An example of such an instance with three agents of uniform budget b = 1 is given in Figure 4. We now give a construction for an arbitrary number of agents k and an evaluation for each p ∈ V ∪ i S(i):

Define G = (V, E, ω) with uniform edge weights ω = 1 as follows: For each agent i, we connect its starting position p i to nodes u i,j , ∀1 ≤ j ≤ k.

Furthermore, we connect each node u i,i to all nodes u j,i , ∀ 1 ≤ j ≤ k. We also add edges {u i,i , u j,j }, ∀ 1 ≤ i < j ≤ k, such that the k nodes u • p = u a,a : Agent a will move to c p a = u a,a , while every other agent j is indifferent between u j,j and u j,a and thus might move to c p j = u j,a . In this case, agents i • p = p a : Agent a will stay on p a , while every other agent j is indifferent between u j,j and u j,a . In case they each choose c p j = u j,a , we get a configuration C p where any two agents i, j have distance 2., giving

= j have distance d(c p i , c p j ) = 1 if i = a or j = a and d(c p i , c p j ) = 2 otherwise, giving Sum(C p ) = 2(k-1)•1+(k-1)(k-2)•2 = 2(k -1) 2 = 2 k-1 k k(k -1) = 2(1 -1 k ) • Sum(O). • p = u a
Sum(C p ) = 2k(k -1) = 2 • Sum(O).
Hence the approximation analysis of Algorithm 3 is tight.

Theorem 7. There is no FPTAS for MinSum, unless P = NP.

Proof. Assume for the sake of contradiction that there is a polynomial-time approximation scheme for MinSum which for all ε > 0 computes a (1 + ε)approximation in time poly(k, 1 ε ). We reuse the reduction to 3Sat already given in Theorem 5. Recall from its proof that (i) the underlying 3Satformula φ is satisfiable if and only if there is a Near-Gathering solution C * in which all agents have pairwise distance 1, and that (ii) any other solution C has at least one pair of agents with distance 2.

mation algorithm for MinDiam with arbitrary stops, unless P = NP.

(Proof at end of Section.)

This is surprising for two reasons. On the one hand, not moving the agents at all is already an additive +(2 max i b i )-approximation. On the other hand, this is the only result in this paper, in which the two scenarios of (I) node Finally, we aim to study the reverse problem of Spreading energy-constrained mobile agents, with the respective goals of (i) maximizing the radius of a smallest ball containing all agents, (ii) maximizing the minimum distance between any two agents, and (iii) maximizing the average distance between any two agents.

We finish by proving the additive approximation hardness results in Theorem 8 by a similar reduction from 3Sat as the one given for the multiplicative (2 -o(1))-approximation hardness of MinDiam. Instead of a self-contained proof, we describe all necessary adaptions we make in the proof of Theorem 5.

Proof. Given an arbitrary 3Sat formula φ with n variables and m clauses, we first make a one-to-one copy φ of all its variables and all its clauses. Clearly, φ is satisfiable if and only if Φ := φ ∧ φ is satisfiable. We now construct an instance G, k, (p i ) i=1,...,k , (b) i=1,...,k with k = 2n + 2m agents of uniform budget b and a graph G = (V, E, ω) in the same manner as for Theorem 5.

We add weights to the edge of G in the following manner: the weight of each edge in E x ∪E CL is b and the weight of each edge in E ∪E L ∪E LL is 2b.

Overall, the main reduction idea is now the following: Φ shall be satisfiable if and only if there is an optimum solution of diameter 2b. Furthermore, from any configuration with a "good" additive approximation and small diameter, we can infer either a satisfiable assignment of φ or of φ . ⇐ We now show that if Φ is not satisfiable, then every solution to Min-Diam with node stops is of size greater than or equal to 2b + 2b = 4b.

The difficulty lies in the fact that Lemma 4 is no longer valid, since the node triples v i , v T i , v F i no longer form an equilateral triangle; instead, we have ω({v T i , v F i }) = 2b, while v i is connected to v T i , v F i with two edges of weight b.

Similarly, edges in E LL have weight 2b while edges in E CL have weight b.

We now observe the following: If in a configuration C there are two agents i, j which stay on their starting position p i , p j , then they must have a distance of d(p i , p j ) ≥ b + 2b + b = 4b. Otherwise, there is at most one agent staying at its starting position. Thus in at least one of the subgraphs induced by φ and φ , respectively, we can assume that all agents move to nodes in V ∪ V L . Repeating the arguments given in the proof of Theorem 5, since φ and φ are not satisfiable, there must be two agents in V and V L which are not connected by an edge and thus have distance at least 2b + 2b = 4b.

⇐ We now show that if Φ is not satisfiable then every solution to Min-Diam with arbitrary stops is of size greater than or equal to 2b +

Feasible solution:

  Any configuration C = (c 1 , . . . , c k ) of agent end positions c i , in which for each agent i, 1 ≤ i ≤ k, we have d(p i , c i ) ≤ b i . In the node-stop variant, we additionally require c i ∈ V . Goals: (i) MinBall: Minimize Radius(C, c) of a smallest ball containing C around an optimally chosen center c, where Radius(C, c) = max i d(c, c i ).

Lemma 1 .

 1 The sets B(i), S(i) and M (S) can be computed in time polynomial in |V |, k and |V |, |S|, respectively. Proof. For each agent i, we find the ball B(i) of all reachable nodes by computing a single-source shortest paths tree from p i in O(|V | 2 ). The sphere S(i) contains at most two points per edge e = {u, v} which can be found in constant time given knowledge of the edge weight ω(e) and the already computed node distances d(p i , u), d(p i , v). Overall the 2k many sets B(i), S(i) are of size O(|V |) and O(|V | 2 ), respectively, and can be computed in time O(k|V | 2 ).

Theorem 1 (Lemma 2 .

 12 MinBall, node centers). Algorithm 1 is a polynomial-time algorithm for MinBall with node centers. The polynomial running time of Algorithm 1 follows immediately from the fact that B(i), S(i) can be computed in polynomial time and have polynomial size by Lemma 1. As the algorithm iterates over all possible center nodes, we can establish correctness by characterizing optimum stopping positions: There exists an optimum solution (O, o) for MinBall where every agent i either stops on the center o or on a point in B(i) ∪ S(i), independent of whether o is contained in i (B(i) ∪ S(i)) or not. Proof. Assume that there is no such optimum solution and denote by C * = (c * 1 , c * 2 , . . . c * k ) and c * a solution with a minimum number of points c * i / ∈ B(i) ∪ S(i) ∪ {c * } among all optimum solutions. We take any agent a with c * a / ∈ B(a) ∪ S(a) ∪ {c * }. By definition of B(a) and S(a), c * a must be a point inside an edge for which d(p a , c * a ) < b a . Without loss of generality we may assume that a reached c * a by moving along a shortest path from p a to c * . Hence it still has energy left to move further along the shortest path towards c * . We move agent a until it reaches a point in B(a) ∪ {c * } or until its energy is depleted, in which case it will have reached a point in S(a). The new configuration has smaller or equal radius, and also a strictly smaller number of points c * i / ∈ B(i) ∪ S(i) ∪ {c * }, contradicting the minimality of C * . Hence there is always an optimum solution adhering to Lemma 2.

  Let e = {u, v} ∈ E be the edge-subdivision containing c, c ∈ seg(e), and denote by A u , A v the set of agents i with stopping positions c i = c that entered e via u or v, respectively. Without loss of generality, each agent i ∈ A u ∪ A v has reached c along a shortest p i -c-path and, since c i = c / ∈ S(i), has a remaining energy of b i -d(p i , c i ) > 0. We first assume that A u ∪ A v contains all k agents. In this case we move the center c and all agent stopping positions C to u, yielding a new center node c * := u ∈ V ∪ i S(i) and configuration C * = (c * , . . . , c * ) with radius Radius(C * , c * ) = 0. Note that for each agent i ∈ A u we have d(p i , c * ) < d(p i , c) and for each agent j ∈ A v we have -since there is no point p ∈ seg({c, u}) with p ∈ B(j) ∪ S(j) -that d(p j , c * ) ≤ b j . Hence C * is a feasible configuration and (C * , c * ) an optimum solution. Otherwise denote by c a ∈ B(a) ∪ S(a) the agent stopping position with maximum distance d(c a , c) among all configuration points which have a shortest path to c containing u. Analogously, denote by c b ∈ B(b) ∪ S(b) the furthest agent stopping position among all configuration points which have a shortest path to c containing v. Since c / ∈ M (V ∪ i S(i)), we know Algorithm 2 MinBall (arbitrary centers), MinDiam (2-apx / on Trees) Input: An instance G, k, (p i ) i=1,...,k , (b i ) i=1,...,k . Output: Configuration C, center c ∈ G with minimum radius Radius(C,

  that d(c, c a ) = d(c, c b ). Thus we can move c together with all agent stopping positions c i = c (of agents i ∈ A u ∪ A v that have stopped on c) by a small distance of ε > 0 towards the further of the two positions c a , c b . This still gives a feasible solution (C * , c * ) that has strictly smaller radius Radius(C * , c * ) = max{d(c, c a ), d(c, c b )} -ε, contradicting the optimality of (C, c). The cases where only c a or only c b is defined can be treated analogously.

Theorem 3 (

 3 MinDiam, 2-apx). Algorithm 2 is a polynomial-time 2-approximation algorithm for MinDiam. Proof. Let configuration C * = (c * 1 , . . . , c * k ) with center c * be the MinBall solution computed by Algorithm 2. We denote the radius of (C * , c * ) by r * = Radius(C * , c * ) = max j d(c * , c * j ) and the diameter of C * by d * = Diam(C * ) = max i,j d(c * i , c * j ). Using the triangle inequality, we have for all configuration

2 b2=1Figure 1 :

 21 Figure 1: (left) MinDiam-instance with (unique) optimum solution O = (o 1 , o 2 , o 3 ) of diameter Diam(O) = 8, in which we have final positions o 3 / ∈ B(3) ∪ S(3) and o 2 / ∈ M (V ∪ i S(i)). (right) Replacing Radius(C p , p) in Lines 5&7 of Algorithm 2 with Diam(C p ) (yielding configurations depicted by × vs , with diameters 2 and 1, respectively) improves the quality of a MinDiam solution for certain instances by a factor of 2.

  i , p j ) -b i -b j for arbitrary final positions. We show that, indeed, Algorithm 2 computes a configuration C * with diameter Diam(C * ) = d * . To this end, denote by a, b two agents giving rise to d * , and let q a ∈ B(a) ∪ S(a), q b ∈ B(b) ∪ S(b) be two points with d(q a , q b ) = d * .

Figure 1 (Theorem 5 .

 15 Figure1(right). However, this does not translate to the worst-case approximation guarantee, as one can see in the instance constructed in the following matching approximation hardness result. Theorem 5. There exists no deterministic polynomial-time 2-o(1) -approximation algorithm for MinDiam, unless P = NP. This holds even in unweighted graphs with uniform budgets b i = 1, i = 1, . . . , k.We will prove Theorem 5 by a reduction from 3Sat along the following lines: First, given any 3Sat instance, we construct a MinDiam instance with variable agents and clause agents. Next, we present a structural result (Lemma 4), from which we can infer that each variable agent will always move to either a node representing its positive literal or a node representing its negative literal; similarly, we infer that each clause agent will move to a node representing a possible truth assignment of the respective clause. Finally, we prove Theorem 5 by showing that satisfiable 3Sat instances admit a MinDiam solution of diameter 1, while unsatisfiable 3Sat instances result in instances with optimum MinDiam solutions of diameter at least 2.

  are nodes corresponding to literals, i.e. true-value and false-value assignments of the variables x i , • V C = {c j | 1 ≤ j ≤ m} are nodes corresponding to clauses C 1 , . . . , C m , • V L = {c l j | 1 ≤ j ≤ m, ∀l ∈ L} are nodes corresponding to all possible truth assignments of each clause C i .

Figure 2 :

 2 Figure 2: A part of an instance of MinDiam, constructed from the 3-SAT instance C 1 ∧ • • • ∧ C m with variables x 1 , . . . , x n , displaying the connections between nodes v 1 , v 2 , v n , c 1 and c m . Notice that nodes c FFT 1

  m

Lemma 4 .

 4 For any configuration C = (c 1 , . . . , c k ) with an agent i for whichc i / ∈ V ∪ V L ,there exists another configuration C = (c 1 , . . . , c k ) with diameter Diam(C ) ≤ Diam(C ) for which ∀i :

y

  are not connected by an edge. Moreover, the shortest path between nodes c y and c FTF y is equal to 2 (via edges in E CL and E LL ). Therefore, agent a(c y ) cannot reach node c FTF y . Any other node c l y , where l ∈ L \ {FTF}, to which agent a(c y ) could relocate, corresponds to a truth assignment to x r , x s and x t where at least one of the variables has the opposite value of its assignment. Say that a(c y ) chooses to move to node c TTF y , then a(c y ) will have a distance of 2 from agent a(v r ) since a(v r ) has moved to node v F r . Recall that node v F r is not connected by an edge to node c TTF y , since x r appears in C y but v F r does not agree with c TTF y . Therefore, agents a(c y ) and a(v r ) will have a distance of 2.

  among all optimum configurations of O . Denote by A = the set of all agents j with stopping point c * j = c * . Since c * / ∈ V ∪ i S(i), we must have d(p j , c * j ) < b j for all agents j ∈ A = . Furthermore, since c * / ∈ V , c * ∈ seg(e) for some edge {u, v}. Denote by A u the set of all agents j for which c * j ∈ seg(e) and c * j is between u and c * in seg(e), or for which there is a shortest path from c * j to c * going through u. Denote by A v the set of all agents j / ∈ A = ∪ A u (for which, there must be a shortest path from c * j to c * going through v, or for which c * j ∈ seg(e) and c * j is between v and c * in seg(e)). Without loss of generality, we assume |A u | ≥ |A v |. Now consider what happens to Sum(C * ) when we move all stopping points c * j of agents j ∈ A = by an ε > 0 towards u:

  Hence we can move the stopping points c * j of agents j ∈ A = until we reach (i) a point p ∈ V ∪ i S(i) or until we reach (ii) the stopping point p = c * a of another agent a, whichever comes first. In either case, we still have for all agents j ∈ A = that d(p j , p) ≤ b j . Furthermore, in the first case we have found a feasible configuration with a smaller number of agents j such that c j / ∈ V ∪ i S(i), contradicting the minimality of O -configurations among configurations in O. In the second case, we have found a feasible configuration with a larger number of agents stopping on the same point p, contradicting the maximality of C * among configurations in O . Theorem 6 (MinSum, 2(1 -1 k )-apx). Algorithm 3 is a polynomial-time 2(1 -1 k )-approximation algorithm (and the approximation ratio is tight). Proof. (Upper bound). Let C * = (c * 1 , . . . , c * k ) denote the configuration computed by Algorithm 3. We denote with s * := Sum(C * ) the sum of all pairwise agent distances in C * . Furthermore, let O = (o 1 , . . . , o k ) be an optimum MinSum solution in which each agent j stops on a point o j ∈ V ∪ i S(i) and let s Opt = Sum(O) = i j d(o i , o j ). Choosing a point o ∈ arg min o i ∈O j d(o i , o j ) we get j d(o, o

  do

2 :, 3 :

 23 Compute C p := (c p 1 , . . . , c p k )where eitherc p i = p if d(p i , p) ≤ b i , or otherwise 4:

  ,b (for a = b): Agent a will move to c p a = u a,b and agent b to c p b = u b,b . Every other agent j is indifferent between u j,j and u j,b , having both distance 2 to u a,b . In case they each choose c p j = u j,b , we get a configuration C p which is symmetric to the previous case.

  stops and (II) arbitrary stops differ. The difference in the hardness result boils down to the loss of Lemma 4 in the adaption of the proof of Theorem 5, which we can only fully salvage for the case of node stops. Does this mean that there is a polynomial-time +(2 max i b i -o(1))-approximation for the scenario with arbitrary final positions? This remains completely open.

⇒

  We first show that if Φ is satisfiable, then there exists an optimum configuration C of diameter Diam(C) = 2b. This follows immediately from the proof of Theorem 5. Since we increased the weight of all relevant edges by a factor or 2b, we get with the same reasoning an optimum configuration C of diameter Diam(C) = 2b (instead of the previously shown 1).

  As in the case of node stops, we note that if in a configuration C there are two agents i, j which move away from their starting positions p i , p j by a distance of at most δ := b 3 , then they must have a distance of at least d(p i , p j ) -δ -δ = b + 2b + b -2δ = 10 3 b. Otherwise, there is at most one agent staying closer than δ to its starting position. Thus in at least one of the subgraphs induced by φ and φ , respectively, each agent moves either to a vertex in V ∪ V L or to a point of an edge of E x ∪ E CL at distance at least δ = b 3 from its starting position. Repeating the arguments given in the proof of Theorem 5, since φ and φ are not satisfiable, there must be a variable agent a(v i ) moving towards a node u ∈ V and a clause agent a(c j ) moving towards a node v ∈ V L which are not connected, i.e. {u, v} / ∈ E L . Thus a(v i ) and a(c j ) are connected with a shortest path going via v i or c j and hence have a distance of at least δ + b + 2b = 10 3 b. Since a polynomial-time additive +(2b -o(1))-approximation algorithm for MinDiam with node stops could distinguish between instances with an optimum solution with diameter 2b and instances with an optimum solution with diameter 4b, it would also be able to decide whether Φ is satisfiable of not. Similarly a polynomial-time additive +( 4 3 b -o(1))-approximation algorithm for MinDiam with arbitrary stops could distinguish between instances with an optimum solution with diameter 2b and instances with an optimum solution with diameter 10 3 b. This completes the proof.

  Consider now the configuration C o = (c o 1 , . . . , c o k ) which Algorithm 3 computed for point o in Step 2 and let s o := Sum(C o ) = i j d(c o i , c o j ). Clearly, we have s * ≤ s o . Furthermore, o is reachable by at least one agent a, thus by Step 2 we also have c o a = o. Finally, as Step 2 moves agents as close to o as possible, we have d(o, c o j ) ≤ d(o, o j ). Using the triangle inequality, we rewrite s o to get

	6: end for
	7: Return	arg min	Sum(C p ).
	C p : p∈V ∪ i S(i)

  1,1 , . . . , u k,k induce a k-clique, see Figure 4. As each pair of agents i = j has original distance d(p i , p j ) = 3, every configuration C must have Sum(C) ≥ k(k -1), with equality only for the k-clique O = (u 1,1 , . . . , u k,k ). For every agent i, we have B(i) ∪ S(i) = {p i , u i,1 , . . . , u i,i , . . . , u i,k } and thus V ∪ i S(i) = V . We analyze the configurations C p and Sum(C p ) = i j d(c p i , c p

j ) computed in Lines 2-5 for each round p ∈ V :

$ This work was partially supported by the SNF (project 200021L_156620) and by the ANR (project ANCOR anr-14-CE36-0002-01), while A. Bärtschi was working at ETH Zürich, and E. Bampas and C. Karousatou were working at Aix-Marseille Université. The Los Alamos National Laboratory report number is LA-UR-19-23906.

In the tie-breaking in Line 4, agents i will generally be indifferent between the options u i,i and u i,j , leading to a configuration

Summing up the pairwise distances we get for (i) that Sum(C * ) = k(k -1), while for (ii) we have Sum(C) ≥ k(k -1) + 1. The existence of an FPTAS, using ε ≤ 1 k 2 , means that we can approximate Sum(C * ) to within

Hence we could distinguish the existence of a solution C * from any other solution and thus decide satisfiability of φ in time poly(k, 1 1/k 2 ) = poly(k), in contradiction to the assumption P = NP.

Additive Approximation and Conclusion

In this paper, we explored the task of Near-Gathering a group of energyconstrained agents, whose movements are restricted by their energy budget.

We showed how to compute, in polynomial time, an optimum solution for

MinBall (minimizing the radius of a smallest ball containing all agents), a 2-approximation for MinDiam (minimizing the maximum distance between any two agents), and a 2(1 -1 k )-approximation for MinSum (minimizing the average distance between any two agents). For MinDiam, we provided a matching hardness result, while for MinSum, we ruled out the existence of an FPTAS, unless P = NP. Hence for future work, a major open problem is to improve upon the (in)approximability of MinSum.

A second possible research direction for Near-Gathering is an analysis of additive approximation. For this, we briefly review how we can reuse our hardness construction of multiplicative approximation of MinDiam: