Reallocating Multiple Facilities on the Line

1 Introduction

Facility Location is a classical problem that has been widely studied in both combinatorial optimization and operations research, due to its many practical applications. It provides a natural model for industrial planning, network design, machine learning, data clustering and computer vision [Drezner and Hamacher, 2002; Lazic, 2011; Caragiannis et al., 2016; Betzler et al., 2013]. In its basic form, K-Facility Location instances are defined by the locations of n agents in a metric space. The goal is to find K facility locations so as to minimize the sum of distances of the agents to their nearest facility.

In many natural location and network design settings, agent locations are not known in advance. Motivated by this fact, [Meyerson, 2001] introduced online facility location problems, where agents arrive one-by-one and must be irrevocably assigned to a facility upon arrival. Moreover, the fast increasing volume of available data and the need for responsive services has led to online clustering algorithms [Liberty et al., 2016], trading off the quality against the consistency of the clusters over time. In practical settings related to online data clustering, new data points arrive, and the decision of clustering some data points together should not be regarded as irrevocable (see e.g., [Fotakis, 2011] and the references therein).

More recently, understanding the dynamics of temporally evolving social or infrastructure networks has been the central question in many applied areas such as viral marketing, urban planning etc. Dynamic facility location proposed by [Eisenstat et al., 2014] is a new tool to analyze temporal aspects of such networks. In this time dependent variant of facility location, agents may change their location over time and we look for the best tradeoff between the optimal connections of agents to facilities and the stability of solutions between consecutive timesteps. The stability of the solutions is modeled by introducing an additional moving cost (or switching cost), which has a different definition depending on the particular setting.

In this work, we study the multistage K-facility reallocation problem on the real line, introduced by [de Keijzer and Wojtczak, 2018]. In K-facility reallocation, K facilities are initially located at (x01 , . . . , x0K ) on the real line. Facilities are meant to serve n agents for the next T days. At each day, each agent connects to the facility closest to its location and incurs a connection cost equal to this distance. Agent locations may change every day, thus we have to move facilities accordingly so as to reduce the connection cost. Naturally, moving a facility is not for free, but comes with the price of the distance that the facility was moved. Our goal is to specify the exact positions of the facilities at each day so that the total connection cost plus the total moving cost is minimized over all T days. In the online version of the problem, the positions of the clients at each stage t are revealed only after determining the locations of the facilities at stage t - 1.

For a motivating example, consider a company willing to advertise its products. So, it organizes K advertising campaigns at different locations of a large city for the next T days. Based on planned events, weather forecasts, etc., the company estimates a population distribution over the locations of the city for each day. Then, it decides to compute the best possible campaign reallocation with K campaigns over all days (see also [de Keijzer and Wojtczak, 2018] for more examples).

[de Keijzer and Wojtczak, 2018] fully characterized the optimal offline and online algorithms for the special case of a single facility and presented a dynamic programming algorithm for K ≥ 1 facilities with running time exponential in K. Despite the practical significance and the interesting theoretical properties of K-facility reallocation, its computational complexity and its competitive ratio (for the online variant) are hardly understood.

In this work, we resolve the computational complexity of K-facility reallocation on the real line and take a first step towards a full understanding of the competitive ratio for the online variant. More specifically, in Section 3, we present an optimal algorithm with running time polynomial in the combinatorial parameters of K-facility reallocation (i.e., n, T and K). This substantially improves on the complexity of the algorithm, presented in [de Keijzer and Wojtczak, 2018], that is exponential in K. Our algorithm solves a Linear Programming relaxation and then rounds the fractional solution to determine the positions of the facilities.

Interestingly, the extreme points of the K-facility reallocation polytope (as described in in Figure 2) do not need to be integral. This is true even for the polytope of K-facility location (a.k.a. K-median, where T=1) on the line (see e.g., [de Vries et al., 2007]). Moreover, there are examples of classical optimization problems (e.g. Minimum Spanning Trees, Maximum Bipartite Matching) with integral LP formulations, where the the natural time-evolving LP formulations (which are similar to the LP formulation in Figure 2) are not integral and have large integrality gaps [Gupta et al., 2014]. Our main technical contribution is to show that a simple rounding scheme yields an integral solution that has the exact same cost as the optimal fractional one.

Our second main result concerns the online version of the problem with K = 2 facilities. We start with the observation that online K-facility reallocation problem with K ≥ 2 facilities is a natural and interesting generalization of the classical K-server problem, which has been a driving force in the development of online algorithms for decades. The key difference is that, in the K-server problem, there is a single agent that changes her location at each stage and a single facility has to be relocated to this new location at each stage. Therefore, the total connection cost is by definition 0, and we seek to minimize the total moving cost.

From a technical viewpoint, the K-facility reallocation problem poses a new challenge, since it is much harder to track the movements of the optimal algorithm as the agents keep coming. It is not evident at all whether techniques and ideas from the K-server problem can be applied to the K-facility reallocation problem, especially for more general metric spaces. As a first step towards this direction, we design a constantcompetitive algorithm, when K = 2. Our algorithm appears in Section 4 and is inspired by the double coverage algorithm proposed for the K-server problem [Koutsoupias, 2009].

We can cast the K-facility reallocation problem as a clustering problem on a temporally evolving metric. From this point of view, K-facility reallocation problem is a dynamic K-median problem. A closely related problem is the dynamic facility location problem, [Eisenstat et al., 2014; An et al., 2017]. Other examples in this setting are the dynamic sum radii clustering [Blanchard and Schabanel, 2017] and multi-stage optimization problems on matroids and graphs [Gupta et al., 2014].

In [Friggstad and Salavatipour, 2011], a mobile facility location problem was introduced, which can be seen as a one

Figure 1: Formulation of K-facility reallocation

stage version of our problem. They showed that even this version of the problem is NP-hard in general metric spaces using an approximation preserving reduction to K-median problem.

Online facility location problems and variants have been extensively studied in the literature, see [Fotakis, 2011] for a survey. [Div´eki and Imreh, 2011] studied an online model, where facilities can be moved with zero cost. As we have mentioned before, the online variant of the K-facility reallocation problem is a generalization of the K-server problem, which is one of the most natural online problems. [Koutsoupias, 2009] showed a (2K - 1)-competitive algorithm for the K-server problem for every metric space, which is also K-competitive, in case the metric is the real line [Bartal and Koutsoupias, 2000]. Other variants of the K-server problem include the (H,K)-server problem [Bansal et al., 2017; Bansal et al., 2018], the infinite server problem [Coester et al., 2017] and the K-taxi problem [Fiat et al., 1990; Coester and Koutsoupias, 2019].

2 ProblemDefinition and Preliminaries

Definition 1 (K-Facility Reallocation) We are given a tuple (x0 ,C) as input, where the vector x0 = (x01 , . . . , x0K ) describes the initial positions of the facilities. The positions of the agents over time are described by C = (C1, . . . , CT ). The position of agent i at stage t is αt i and Ct = (αt1 , . . . , αtn ) describes the positions of the agents at stage t.

Definition 2 A solution of K-Facility Reallocation Problem is a sequence x = (x1 , . . . , xT ). Each xt = (xt1 , . . . , xtK ) is a K dimensional vector that gives the positions of the facilities at stage t and xtk is the position of facility k at stage t. The cost of the solution x is

Given an instance (x0 ,C), the goal is to find a solution x that minimizes the Cost(x). The term ∑Tt=1 ∑Kk=1 |xtk - xt-1 k | describes the cost for moving the facilities from place to place and we refer to it as moving cost, while the term ∑Tt=1 ∑ni=1 min1≤k≤K |αt i - xtk | describes the connection cost of the agents and we refer to it as connection cost.

In the online setting, we study the special case of 2facility reallocation problem. We evaluate the performance of our algorithm using competitive analysis; an algorithm is c-competitive if for every request sequence, its online performance is at most c times worse (up to a small additive constant) than the optimal offline algorithm, which knows the entire sequence in advance. Due to space limitations, most proofs are omitted and can be found in https://128.84.21.199/pdf/1905.12379.pdf.

3 Polynomial Time Algorithm

Our approach is a typical LP based algorithm that consists of two basic steps.

• Step 1: Expressing the K-Facility Reallocation Problem as an Integer Linear Program.
• Step 2: Solving fractionally the Integer Linear Program and rounding the fractional solution to an integral one.

3.1 Formulating the Integer Linear Program

A first difficulty in expressing the K-Facility Reallocation Problem as an Integer Linear Program is that the positions on the real line are infinite. We remove this obstacle with help of the following lemma proved in [de Keijzer and Wojtczak, 2018].

Lemma 3.1 Let (x0, C) an instance of the K-facility reallocation problem. There exists an optimal solution x∗ such that for all stages t ∈ {1, T} and k ∈ {1, K},

According to Lemma 3.1, there exists an optimal solution that locates the facilities only at positions where either a agent has appeared or a facility was initially lying. Lemma 3.1 provides an exhaustive search algorithm for the problem and is also the basis for the Dynamic Programming approach in [de Keijzer and Wojtczak, 2018]. We use Lemma 3.1 to formulate our Integer Linear Program.

The set of positions Pos = C1 ∪ . . . ∪ CT ∪ x0 can be represented equivalently by a path P = (V,E). In this path the j-th node corresponds to the j-th leftmost position of Pos and the distance between two consecutive nodes on the path equals the distance of the respective positions on the real line. Now, the facility reallocation problem takes the following discretized form: We have a path P = (V, E) that is constructed by the specific instance (x0 , C). Each facility k is initially located at a node j ∈ V and at each stage t, each agent i is also located at a node of P. The goal is to move the facilities from node to node such that the connection cost of the agents plus the moving cost of the facilities is minimized.

To formulate this discretized version as an Integer Linear Program, we introduce some additional notation. Let d(j, l)

Algorithm 1: Algorithm for the offline case

Data: Given the initial positions x0 = {x01 , . . . , x0K } of the facilities and the positions of the agents C = {C1, . . . , CT }.

• Build the path P and the Integer Linear Program (1).
• Solve the relaxation of the Integer Linear Program (1).
• Rounding 1 : For each stage t ≥ 1:
• For m = 1, . . . ,K, find the node j tm such that ∑j tm-1 ℓ=1 ctℓ ≤m-1 ≤ ∑j tm ℓ=1 ctℓ
• Set facility m at the respective position of node j tm on the line, xtm ← d(j, 1) + minp∈C1∪...∪CT ∪x0 p.

be the distance of the nodes j, l ∈ V in P, F be the set of facilities and C be the set of agents. For each i ∈ C, Loc(i, t) is the node where agent i is located at stage t. We also define the following {0, 1}-indicator variables for all t ∈ {1, T}: xtij = 1 if, at stage t, agent i connects to a facility located at node j, f tkj = 1 if, at stage t, facility k is located at node j, Stkjl = 1 if facility k was at node j at stage t - 1 and moved to node l at stage t. Now, the problem can be formulated as the Integer Linear Program depicted in Figure 1.

The first three constraints correspond to the fact that at every stage t, each agent i must be connected to a node j where at least one facility k is located. The constraint ∑j∈V f tkj = 1 enforces each facility k to be located at exactly one node j. The constraint Stk = ∑j,l∈V d(j, l)Stkjl describes the cost for moving facility k from node j to node l. The final two constraints ensure that facility k moved from node j to node l at stage t if and only if facility k was at node j at stage t - 1 and was at node l at stage t (Stkjl = 1 iff f tkl = 1 and f t-1 kj = 1).

We remark that the values of f 0 kj are determined by the initial positions of the facilities, which are given by the instance of the problem. The notation xtij should not be confused with xtk that is the position of facility k at stage t on the real line .

3.2 Rounding the Fractional Solution

Our algorithm, described in Algorithm 1, is a simple rounding scheme for the optimal fractional solution of the ILP of Figure 1. This simple scheme produces an integral solution that has the exact same cost with the optimal fractional solution.

Lemma 3.2 Let x denote the solution produced by Algorithm 1. Then,

where xtij , Stk denote the values of these variables in the optimal fractional solution of the Integer Linear Program (1).

Lemma 3.2 is the main result of this section and it implies the optimality of our algorithm. We remind that by Lemma 3.1 there is an optimal solution that locates facilities only in positions C1 ∪ . . . ∪ CT ∪ x0 . This solution corresponds to an integral solution of our Integer Linear Program, meaning that Cost(x∗ ) is greater or equal than the cost of the optimal fractional solution, which by Lemma 3.2 equals Cost(x).

We dedicate the rest of the section to sketch the key steps towards proving Lemma 3.2. The technical detailes are omitted due to lack of space. Putting technicalities aside, the proof is based on a simple and intuitive observation. For the rest of the section, ctj , xtij , f t j , Stkjl will denote the values of these variables in the optimal fractional solution of the ILP (1).

Definition 3 V + t denotes the set of nodes of P with a positive amount of facility at stage t. Formally,

Nodes in V + t are ordered from left to right and when we refer to the j-th node of V + t , we mean the j-th left most node.

Observation 1 The set of nodes at which agent i connects at stage t are consecutive nodes of V + t .

The term consecutive nodes of V + t has the following interpretation: every node j ∈ V between two of the consecutive nodes of V + t either belongs to the these consecutive nodes of V + t or does not belong to V + t . Observation 1 follows from the fact that at any stage t, agent i connects to the nodes of V + t that are closest to Loc(i, t) and have a total amount of facility (ctj ) at least 1. It is not hard to see that if these nodes are not consecutive nodes of V + t , then the connection cost of i at stage t can be decreased, which contradicts the optimality of the optimal fractional solution. We use Observation 1 to prove Lemma 3.2 under the following assumption.

Assumption 1 Let f t jk and ctj be either 1/N or 0 for some positive integer N.

Assumption 1 is not satisfied in general by the fractional solution of the LP (1). Actually, each Stkjℓ is either 0 or Atkjℓ /N tkjℓ , for some positive integers Atkjℓ ,N tkjℓ , and each positive f tkj is of the formBtkj /N, where N = ΠStkjℓ>0N tkjℓ (since f tkj = ∑j∈V Stkjℓ ).

However, starting from a fractional solution of the LP (1), we can enforce Assumption 1 for a (possibly exponentially) large N, if we create enough collocated copies of each point (j, t) and equi-distribute the values of f t jk and ctj over them. The crucial observation is that We need Assumption 1 just to simplify the analysis. After we show (i) how to transform a fractional solution so that it satisfies Assumption 1 ; and (ii) that under Assumption 1, Algorithm 1 computes an optimal integral solution, we observe that the facility locations of Algorithm 1 can be derived from the fractional solution in linear time. In the following, show that under Assumption 1, Algorithm 1 computes an integral optimal solution with cost no larger than the cost of the initial fractional solution.

We note that |V + t | =KN, since there are exactly K facilities. By Assumption 1, each facility k places an amount of facility 1/N to exactly N nodes of V + t at each stage t. Now, observe that the connection cost only depends on the values ctj , meaning that the matching between facilities and nodes of V + t only influences the moving cost of the optimal fractional solution. Thus, the optimal fractional solution chooses this matching so as to minimize the fractional moving cost. This optimal matching is the one presented in Statement 1.

Statement 1 Let the facilities be ordered from left to right according to their initial positions. The m-th facility places amount of facility f tmj = 1/N from the (m- 1)N + 1 to the mN node of V + t , ∀t ≥ 1.

Now, consider the following N integral solutions: The p-th solution locates at stage t, facility m at the (m-1)N+p node of V + t . These integral solutions are denoted as {Solp}Np=1 and notice that Algorithm 1 produces Sol1.

Let MovCostti (Solp), ConCostti (Solp) denote the moving cost of the facilities and the connection cost of agent i at stage t in the integral solution Solp respectively. By the construction of the above integral solutions and by Statement 1, the following equality follows:

Now, Observation 1 comes into play: each agent i connects to N consecutive nodes of V + t . We denote this set of nodes as V + ti . By the construction of the solutions {Solp}Np=1 , each Solp locates exactly one facility to exactly one node of V + ti . Moreover, xtij = 1/N for all j ∈ V + ti , since by Assumption 1, ctj = 1/N or 0. Using the last two facts, one can prove that:

Summing Equation (2) over all i and t, and adding it to Equation (1) gives us, that 1N ∑Np=1 Cost(Solp) equals

Since every Cost(Solp) is at least the fractional optimal cost, we immediately obtain Lemma 3.2 (Sol1 is the solution produced by Algorithm 1).

4 AConstant-Competitive Algorithm

In this section, we present an algorithm for the online 2-facility reallocation problem and we discuss the core ideas that prove its performance guarantee.

Our algorithm (Algorithm 2) consists of two major steps. In Step 1, facilities are initially moved towards the positions of the agents. We remark that in Step 1, the final positions of the facilities at stage t are not yet determined. The purpose of this step is to bring at least one facility close to the agents. This initial moving consists of three cases (see Figure 2), depending only on the relative positions of the facilities at stage t-1 and the agents at stage t.

In Step 2, our algorithm determines the final positions of the facilities xt1 , xt2 . Notice that after Step 1, at least one of the facilities is inside the interval [αt1 , αtn ], meaning that at least one of the facilities is close to the agents. As a result, our algorithm may need to decide between moving the second facility close to the agents or just letting the agents connect to the facility that is already close to them. Obviously, the first choice may lead to small connection cost, but large moving cost, while the second has the exact opposite effect. Roughly speaking, Algorithm 2 does the following: If the connection cost of the agents, when placing just one facility optimally, is not much greater than the cost for moving the second facility inside [αt1 , αtn ], then Algorithm 2 puts the first facility to the position that minimizes the connection cost, if one facility is used. Otherwise, it puts the facilities to the positions that minimize the connection cost, if two facilities are used. The above cases are depicted in Figure 3. We formalize how this choice is performed, introducing some additional notation.

Definition 4 · Ct = {αt1 , . . . , αtn } denotes the positions of the agents at stage t ordered from left to right. If |Ct| = 2k, k ∈ N>0, then MC is the interval [αtn/2 , αtn/2+1 ]. If |C| = 2k + 1, k ∈ N0, then MC is a single point.

• H(C) denotes the optimal connection cost for the set C when all agents of C connect to the just one facility. That is H(C) = ∑α∈C |α - MC |. We also define H(∅) = 0.
• C ∗ 1t (resp. C ∗ 2t ) denotes the positions of the agents that connect to facility 1 (resp. 2) at stage t in the optimal solution x∗ . C1t (resp. C2t) denotes the positions of the agents that connect to facility 1 (resp. 2) at stage t in the solution produced by Algorithm 2.

Despite its lengthy description, Algorithm 2 is rather simple. Only the last two cases are difficult to handle, and we explain them subsequently. The performance guarantee of Algorithm 2 is formally stated in Theorem 4.1.

Theorem 4.1 Let x = {xt1 , xt2 }t≥1 the solution produced by Algorithm 2 and x∗ the optimal solution. Then,

where x01 , x02 are the initial positions of the servers.

We remark that the factor 63 in Theorem 4.1 can be improved to 20, but this requires considering some additional cases that are omitted for the sake of exposition. The rest of the section is dedicated to provide a proof sketch of Theorem 4.1. Before proceeding, we present Lemma 4.2 that is a key component in the subsequent analysis and reveals the real difficulty of the online 2-facility reallocation problem.

Lemma 4.2 Let the optimal solution x∗ and C ∗ 1t , C ∗ 2t the set of agents that connect respectively to facility 1 and 2 at stage t. Let the solution yt = (yt1 , yt2 ) defined as follows:

Then the following inequality holds,

Lemma 4.2 indicates that the real difficulty of the problem is not determining the exact positions of the facilities in the optimal solution, but to determine the service clusters that the optimal solution forms. In fact, if we knew the clusters C ∗ 1t , C ∗ 2t

Algorithm 2: Selecting xt1 and xt2

Data: At stage t ≥ 1 the new positions of the agents Ct = {αt1 , . . . , αtn }, ordered from left to right, arrive Step 1: Moving the facilities towards the agents z1 ← xt-1 1 , z2 ← xt-1 2 if z1 > αtn then move facility 1 to the left until it hits αtn z1 ← αtn end if z2 < αt1 then move facility 2 to the right until it hits αt1 z2 ← αt1 end if z1 < αt1 and z2 > αtn then move facility 1 to the right and facility 2 to the left until a facility hits [αt1 , αtn ] z1 ← z1 + min(|xt-1 1 -αt1 |, |xt-1 2 -αtn |) z2 ← z2 - min(|xt-1 1 -αt1 |, |xt-1 2 -αtn |)

end

if αt1 ≤ z1 ≤ αtn and z2 - αtn ≥ 3H(Ct) then put facility 1 to the median of Ct and move facility 2 to the left by 3H(Ct) xt1 ← MCt , xt2 ← z2 - 3H(Ct) end if αt1 ≤ z2 ≤ αtn and αt1 - z1 ≥ 3H(Ct) then put facility 2 to the median of Ct and move facility 1 to the right by 3H(Ct) xt1 ← z1 + 3H(Ct), xt2 ← MCt end else Compute the optimal partition (O1,O2) of Ct that minimizes the connection cost at stage t. Put facility 1 to the median of O1 and facility 2 to the median of O2. xt1 ← MO1 , xt2 ← MO2

then Lemma 4.2 provides us with a 3-approximation algorithm. Obviously, this information cannot be acquired in the online setting, since C ∗ 1t , C ∗ 2t depend on the future positions of the agents that we do not know. We prove that Algorithm 2 has an approximation guarantee of 21 with respect to the solution y, that directly translates to an approximation guarantee of 63 with respect to Cost(x∗ ). The latter is formally stated in Lemma 4.3 and is the main result of this section.

Lemma 4.3 Let x = {xt1 , xt2 }t≥1 be the solution produced by Algorithm 2. Then, the cost paid by solution x at stage t, ∑2k=1 |xtk - xt-1 k | + ∑ni=1 mink=1,2 |xtk -αt i |, is at most

If both facilities 1 and 2 are on the left of the agents, then facility 2 is moved to the right until hitting the position of the leftmost agent (the case with facilities 1 and 2 on the right of agents is symmetric).

If facility 1 is on the left of the agents and facility 2 is on the right of the agents, then both facilities are moved with the same speed towards the interval [αt1, αtn] until one of them hits the interval.

Figure 2: Step 1 of Algorithm 2 is depicted.

Lemma 4.3 directly implies Theorem 4.1 by applying a telescopic sum over all t and then applying Lemma 4.2. Notice that the additive term |x01 - x02 | in Theorem 4.1 comes from the fact that Φ0(x0 ) = |x01 - x02 |.

In the rest of the section, we present the proof ideas of Lemma 4.3, which come together with explaining Steps 1 and 2 of our algorithm. In Step 1, note that since x01 ≤ x02 , then xt1 ≤ xt2 by our algorithm construction. Now, assume that xt-1 2 ≤ αt1 (second case). Before deciding the exact positions of the facilities, we can safely move facility 2 to the right until reaching αt1 . The term safely means that this moving cost is roughly upper bounded by the moving cost ∑2k=1 |ytk - yt-1 k |. This safe moving applies to all three cases of Step 1 in Algorithm 2 and is formally stated in Lemma 4.4.

Lemma 4.4 Let z = (z1, z2) denote the values of the variables z1, z2 after Step 1 of Algorithm 2. Then,

Proof: Assume that xt-1 2 ≤ αt1 . Then, Algorithm2 will first move facility 2 to αt1 (z1 = xt-1 1 , z2 = αt1 ), paying moving cost equal to |αt1 -xt-1 2 |. This moving cost can be bounded with the use of the potential function Φ. More specifically, we have that Φt(z) - Φt(xt-1 ) + Φt(xt-1 ) - Φt-1(xt-1 ) ≤ Φt(z) - Φt(xt-1 ) + 2 ∑2k=1 |ytk - yt-1 k |.

In case where z1 = xt-1 1 , z2 = αt1 , the difference Φt(z) - Φt(xt-1 ) in the potential function equals 2(|yt2 -αt1 | - |yt2 - xt-1 2 |) + |xt-1 1 -αt1 | - |xt-1 1 - xt-1 2 |. By the definition of solution y in Lemma 4.3, either yt1 or yt2 lies in the interval [αt1 , αtn ]. The latter implies that yt2 is on the right of αt1 . As a result we have that Φt(z) - Φt(xt-1 ) = -|z2 - xt-1 2 |, which completes the proof of Lemma 4.4 for this case of Step 1.

Notice that inequality (3) holds for all three cases of Step 1. Thus, one just need to prove that Φt(z) - Φt(xt-1 ) ≤ - ∑2k=1 |zk - xt-1 k | for the other two cases. The case xt-1 1 ≥ αtn is just symmetric. Since either either yt1 or yt2 is in [αt1 , αtn ], it can be easily shown that Φt(z)-Φt(xt-1 ) ≤ - ∑2k=1 |zk - xt-1 k | for the third case of Step 1. □

2

The second choice of Step 2 is depicted. Facilities are placed to the positions, where the connection cost of the agents is minimized using two facilities.

Figure 3: Step 2 of Algorithm 2 is depicted.

The proof of Lemma 4.4 reveals the basic idea in Step 1. According to the geometry of the agents' positions, we can identify a safe move whose cost is also paid by solution y for moving the servers. Moreover, this proof reveals why we compare our algorithm with the solution y and not directly with x∗ . All these safe moves are based on the fact that either yt1 or yt2 lies in the [αt1 , αtn ] (the latter does not necessarily hold for x∗ ). Finally, the potential function Φt(x1, x2) is crucial, since it permits safe moves, when all agents are on the right/left of the facilities (first/second case) as well as when they are contained in the interval [xt-1 1 , xt-1 2 ] (third case). This idea was developed for the K-server problem [Koutsoupias, 2009].

Up next, we analyze the ideas of Step 2. We now need to bound the connection cost plus some additional moving cost from the point where the safe move stopped.

Lemma 4.5 Let xt = (xt1 , xt2 ) denote the locations of facilities at stage t after the execution of Step 2. Then,

The proof of Lemma 4.5 is again based on the function Φt(x1, x2). The difficult case is when y served the agents using both facilities, since y's connection cost can be arbitrarily smaller than H(Ct). The last case of Step 2 is easier, since Algorithm 2 pays minimum connection cost.

Acknowledgements

The names of the authors are in alphabetical order. Loukas Kavouras is partially supported by a scholarship from the State Scholarships Foundation, granted by the action "Scholarships Grant Programme for second cycle graduate studies", which is co-financed by Greece and the European Union (European Social Fund-ESF) through the Operational Programme "Human Resources Development, Education and Lifelong Learning 2014-2020". Stratis Skoulakis is partially supported by a scholarship of Onassis Foundation.