Antje Bjelde

Yann Disser

Jan Hackfeld

Christoph Hansknecht

Maarten Lipmann

Julie Meissner

Kevin Schewior

Miriam Schlöter

Leen Stougie

Julie Meißner

Tight Bounds for Online TSP on the Line

niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

In the online Traveling Salesperson Problem (TSP) on the line, we consider a server initially located at the origin of the real line that has to serve requests that appear over time. The server has unit speed and serves requests (in any order) by moving to the position of the corresponding request at some time after its release. The objective in online TSP on the line is to minimize the makespan, i.e., the time until all requests have been served. In the closed variant of the problem, the server needs to return to the origin after serving all requests, while the open variant has no such requirement.

Online TSP is a natural online problem similar to the classical k-server problem [START_REF] Manasse | Competitive algorithms for server problems[END_REF]. In the latter, the order in which requests need to be served is prescribed, and the problem thus becomes trivial on the line for k = 1 server. In contrast, online TSP on the line is a non-trivial problem that arises in 1dimensional collection/delivery problems. Examples include robotic welding/screwing/depositing material, horizontal/vertical item delivery systems, and the collection of objects from mass storage shelves. The online Dial-A-Ride problem additionally allows transportation requests that specify a source and destination that need to be visited by the server in this order. If the capacity of the server is finite, it limits the number of requests that can be transported simultaneously. The online Dial-A-Ride problem on the line arises, e.g., when controlling industrial or personal elevators.

While both online TSP and online Dial-A-Ride on the line are among the most natural online problems and have been studied extensively over the last two decades [START_REF] Ascheuer | Online Dial-a-Ride problems: Minimizing the completion time[END_REF][START_REF] Ausiello | Serving requests with on-line routing[END_REF][START_REF] Ausiello | Competitive algorithms for the on-line traveling salesman[END_REF][START_REF] Ausiello | Algorithms for the on-line travelling salesman[END_REF][START_REF] Blom | The online TSP against fair adversaries[END_REF][START_REF] Feuerstein | On-line singleserver Dial-a-Ride problems[END_REF][START_REF] Jaillet | Generalized online routing: New competitive ratios, resource augmentation, and asymptotic analyses[END_REF][START_REF] Krumke | Online optimization competitive analysis and beyond[END_REF][START_REF] Krumke | News from the online traveling repairman[END_REF][START_REF] Krumke | Non-abusiveness helps: An O(1)-competitive algorithm for minimizing the maximum flow time in the online traveling salesman problem[END_REF], no satisfactory (tight) analysis was known for either problem in terms of competitive ratios. We address this shortcoming for TSP on the line by providing a tight upper bound for the closed variant, as well as tight bounds for the open variant. We emphasize that our results for the open and closed variant of the problem are independent and require substantially different approaches. Aside from our results for online TSP, we narrow the gaps for online Dial-A-Ride on the line by giving improved bounds. In addition to online results, we study the computational complexity of the underlying offline problems.

Our results

We have the following results1 (cf. Tables 1 and2) :

Tight bounds for online TSP on the line. Our main results are best-possible online algorithms for both the open and closed variant of online TSP on the line, as well as a new (tight) lower bound for the open variant. Our algorithm for the closed variant has a competitive ratio of (9 + √ 17)/8 ≈ 1.64, matching a lower bound of Ausiello et al. [START_REF] Ausiello | Algorithms for the on-line travelling salesman[END_REF] and improving on their 1.75-competitive algorithm. For open TSP on the line, we give a lower bound of 2.04 on the competitive ratio, which is the first bound strictly greater than 2. We also provide an optimal online algorithm matching this bound and improving on the 2.33-competitive algorithm by Ausiello et al. [START_REF] Ausiello | Algorithms for the on-line travelling salesman[END_REF]. Our results settle online TSP on the line from the perspective of competitive analysis.

Improved bounds for online Dial-A-Ride on the line. Our lower bounds for online TSP on the line immediately apply to preemptive and nonpreemptive online Dial-A-Ride on the line. In particular, our lower bound of 2.04 is the first bound greater than 2 for the open variant of the problem. Additionally, we provide a simple preemptive 2.41-competitive algorithm, which improves a (non-preemptive) 3.41competitive algorithm by Krumke [START_REF] Krumke | Online optimization competitive analysis and beyond[END_REF]. For the closed Dial-A-Ride variant, the lower bound of 1.64 by Ausiello et al. [START_REF] Ausiello | Algorithms for the on-line travelling salesman[END_REF] was improved for one server with unit capacity without preemption to 1.71 by Ascheuer et al. [START_REF] Ascheuer | Online Dial-a-Ride problems: Minimizing the completion time[END_REF]. We improve this bound further to 1.75 for any finite capacity c ≥ 1. The best known algorithm for closed Dial-A-Ride on the line for finite capacity c ≥ 1 is 2-competitive and was given by Ascheuer et al. [START_REF] Ascheuer | Online Dial-a-Ride problems: Minimizing the completion time[END_REF].

New offline complexity results. Regarding offline TSP on the line with release times, Psaraftis et al. [START_REF] Harilaos | Routing and scheduling on a shoreline with release times[END_REF] showed a dynamic program that solves the open variant in quadratic time. We refute their claim that all optimal closed tours have a very simple structure with a counterexample, and we adapt their algorithm to find an optimal closed tour in quadratic time. For the non-preemptive offline Dial-A-Ride problem on the line, results have previously been obtained for the closed variant without release times. For capacity c = 1 Gilmore and Gomory [START_REF] Paul | Sequencing a one state-variable machine: A solvable case of the traveling salesman problem[END_REF] and Atallah and Kosaraju [START_REF] Atallah | Efficient solutions to some transportation problems with applications to minimizing robot arm travel[END_REF] gave polynomial time algorithms, and Guan [START_REF] Jiun | Routing a vehicle of capacity greater than one[END_REF] proved hardness for the case c = 2. We show that both the open and closed variant of the problem are NP-hard for any capacity c ≥ 2. Additionally, we show that the case with release times and any c ≥ 1 is NP-hard. The complexity of offline Dial-A-Ride on the line with unbounded capacity remains open.

Further related work

For the online TSP problem in general metric spaces, Ausiello et al. [START_REF] Ausiello | Algorithms for the on-line travelling salesman[END_REF] show a lower bound of 2 on the competitive ratio for the open version and a 1.64 lower bound for the closed version, both bounds being achieved on the real line. For the open online TSP, they present a 2.5-competitive algorithm, and for the closed version they give a 2-competitive algorithm. Jaillet and Wagner [START_REF] Jaillet | Generalized online routing: New competitive ratios, resource augmentation, and asymptotic analyses[END_REF] give 2-competitive algorithms for the closed version that can additionally deal with precedence constraints or multiple servers. Blom et al. [START_REF] Blom | The online TSP against fair adversaries[END_REF] consider the closed online TSP problem on the non-negative part of the real line and present a best possible algorithm with competitive ratio 1.5. They also study a "fair" setting where the optimum does not travel outside the convex hull of the known requests, and they derive an algorithm for the real half-line with a better competitive ratio of 1.28 for this setting. Krumke et al. [START_REF] Krumke | Non-abusiveness helps: An O(1)-competitive algorithm for minimizing the maximum flow time in the online traveling salesman problem[END_REF] show that there cannot be a competitive algorithm for open online TSP with the objective of minimizing the maximum flow time instead of minimizing the makespan. For the real line they define a fair setting and give a competitive algorithm for it.

The online repairperson problem is the open online TSP problem with the objective of minimizing the weighted sum of completion times. Feuerstein and Stougie [START_REF] Feuerstein | On-line singleserver Dial-a-Ride problems[END_REF] show a lower bound of 5.83 on the bestpossible competitive ratio for this problem and provide a 9-competitive algorithm for the real line. Krumke et al. [START_REF] Krumke | News from the online traveling repairman[END_REF] give a best-possible online algorithm with competitive ratio 5.83 for general metric spaces.

For the the closed online Dial-A-Ride problem without preemption, Feuerstein and Stougie [START_REF] Feuerstein | On-line singleserver Dial-a-Ride problems[END_REF] show a lower bound of 2 for the competitive ratio in general, and present an algorithm with a best-possible competitive ratio of 2 for the case that the server has infinite capacity. Ascheuer et al. [START_REF] Ascheuer | Online Dial-a-Ride problems: Minimizing the completion time[END_REF] analyze For minimizing the sum of completion times instead of the makespan, Feuerstein and Stougie [START_REF] Feuerstein | On-line singleserver Dial-a-Ride problems[END_REF] further show a lower bound of 3 for a server with unit capacity and a lower bound of 2.41 independent of the capacity. Moreover, they provide a 15-competitive algorithm for the real line and unlimited capacity. For the same objective function, Krumke et al. [START_REF] Krumke | News from the online traveling repairman[END_REF] present an algorithm with a competitive ratio of 5.83 for a server with unit capacity in an arbitrary metric space. The offline version of the TSP problem is a wellstudied NP-hard problem (e.g., see [START_REF] Lawler | The Traveling Salesman Problem; A Guided Tour of Combinatorial Optimization[END_REF]). Afrati et al. [START_REF] Afrati | Papadimitriou, George Papageorgiou, and Nadia Papakostantinou. The complexity of the travelling repairman problem[END_REF] show that the offline traveling repairperson problem is NP-hard in general, but can be solved in time O(n 2 ) for the real line and unweighted sum of completion times objective. There are many offline variants of the Dial-A-Ride problem, differing in capacities, the underlying metric space, release times and deadlines, open versus closed tours, and in whether preemption is allowed (e.g., see [START_REF] De Paepe | Computer-aided complexity classification of Dial-a-Ride problems[END_REF]). The special case without release times and unit capacity is known as the stacker crane problem. Attalah and Kosaraju [START_REF] Atallah | Efficient solutions to some transportation problems with applications to minimizing robot arm travel[END_REF] present a polynomial algorithm for the closed, non-preemptive stacker crane problem on the real line. Frederickson and Guan [START_REF] Frederickson | Nonpreemptive ensemble motion planning on a tree[END_REF] show that this problem is NP-complete on trees. Guan [START_REF] Jiun | Routing a vehicle of capacity greater than one[END_REF] shows that the Dial-A-Ride problem remains easy on the line with capacities larger than one if preemption is allowed, and that it remains hard on trees. Finally, Charikar and Raghavachari [START_REF] Charikar | The finite capacity dial-a-ride problem[END_REF] give a O( √ c log n log log n)-approximation for the closed Dial-A-Ride problem in metric spaces with n points and without preemption. In the same paper they claim a 2-approximation for the problem on the line, however this result seems to be incorrect (personal communication).

Problem definition and notation

We consider a server that moves along the real line with (at most) unit speed. We let p t denote the position of the server at time t ≥ 0 and assume (without loss of generality) that p 0 = 0. With this notation, the speed limitation of the server can equivalently be expressed via |p t -p t | ≤ |t -t | for all t, t ≥ 0. A series of requests σ 1 , . . . , σ n arrives over time with σ i = (a i , b i ; t i ), where t i ≥ 0 denotes the release time of the request and a i , b i ∈ R denote its source and target position, respectively. For TSP, we have a i = b i and write σ i = (a i ; t i ). If not stated otherwise, we assume t 1 ≤ t 2 ≤ . . . ≤ t n . Moreover, we assume without loss of generality that t i ≥ |a i | holds because the server can not reach σ i before time |a i | and it only helps the algorithm to know a request earlier. We further use the notation A R := max i=1,...,n {a i , b i , 0} to denote the rightmost point that needs to be visited by the server, and similarly A L := min i=1,...,n {a i , b i , 0}. Here and throughout we refer to the negative direction of the real line as left and the positive direction as right.

In both TSP and Dial-A-Ride on the line, all requests need to be served. For TSP, we consider a request served if p t = a i for some time t ≥ t i . For Dial-A-Ride, the server may collect request σ i at time t ≥ t i if p t = a i . In the preemptive Dial-A-Ride problem, the server can drop off any request it is carrying at its current location at any time. If request σ i is dropped off at point p at time t, we consider it to be modified to the new request (p, b i ; t). In the non-preemptive Dial-A-Ride problem, the server may only drop off a request at its target location. We consider a request served if it is ever dropped off at its target location.

In TSP on the line, the behavior of the server in our algorithms at time t will mostly depend on so-called extreme requests. For t ≥ 0, we denote by σ R (t) = (a R (t); t R (t)) the unserved request that is rightmost of the position of the server p t , provided such a request exists, i.e., the unserved request σ = (a; t ) with t ≤ t, a > p t , and maximizing a. Analogously, σ L (t) = (a L (t); t L (t)) denotes unserved request that is leftmost of the position of the server p t . If there is more than one right-most (left-most) request, we choose the one with the largest release time.

If the server has finite capacity c ≥ 1, it can carry at most c requests at any time. We assume that no time is needed for picking up and dropping off requests, so that the server can pick up and drop off any number of requests at the same time, as long as its capacity is not exceeded.

We refer to a valid trajectory of the server together with the description of when it picks up and drops requests as a tour T . In the offline setting, we assume all requests to be known from the start. We let T Opt denote an optimal offline tour. In the online setting, we assume that request σ i is revealed at its release time t i , at which point the tour of the server until time t i must already have been fixed irrevocably. Additionally, we assume that the total number n of requests is unknown. We measure the quality of an online algorithm via its competitive ratio, i.e., the maximum over all sequences of requests of the ratio between the makespan of the tour it produces and |T Opt |.

In order to describe the trajectory of the server, we use the notation "move(a)" for the tour that moves the server from its current position with unit speed to the point a ∈ R and the notation "waituntil(s)" for the tour that keeps the server stationary until time s. We use the operator ⊕ to concatenate tours. For example, if T 0 is a tour of the server that ends at time t 0 at position p t0 , then T 0 ⊕move(a) describes the tour that ends at time t 0 + |a -p t0 |, is identical to the tour T 0 until time t 0 and satisfies

p t = p t0 + (a -p t0 )(t -t 0 ) for t 0 ≤ t ≤ t 0 + |a -p t0 |. Similarly, T 0 ⊕ waituntil(s)
is the tour that ends at time max{t 0 , s}, is identical to the tour T 0 until time t 0 and that satisfies p t0 = p t for all s ∈ [t 0 , s]. For TSP on the line, we do not explicitly specify when a request is served, but we assume that the server serves a request whenever possible, i.e., whenever the server passes the location of a request that is already released and not yet served.

We skip the proofs of our results as they are very technical. They can be found in the full version of the paper.

Algorithm for closed online TSP

In this section we consider the closed online TSP problem and describe a best-possible algorithm with competitive ratio ρ = (9 + √ 17)/8 ≈ 1.64, where ρ is the nonnegative root of the polynomial 4x 2 -9x + 4.

We start by developing some intuition for our algorithm. In the following T Alg is the tour derived by an algorithm Alg. Observe that the decision of how to move the server at time t only depends on its position p t and the location of the left-and rightmost extreme requests σ L (t) = (a L ; t L (t)) and σ R (t) = (a R ; t R (t)): All other requests can be served during any tour serving σ L (t) and σ R (t). We will show that in this setting we can assume that a L (t) ≤ 0 and a R (t) ≥ 0, provided these extremes exist. If σ R (t) (resp. σ L (t)) does not exist we set a R (t) = t R (t) = 0 (resp. a L (t) = t L (t) = 0). Thus, in contrast to the initial definition of extreme requests, in our setting a leftmost extreme is always left and a rightmost extreme is always right of the origin. When both extremes exists, we have, on a high level, three possible courses of action at time t. Either we immediately decide to serve σ L (t) and σ R (t) in one of the two possible orders, or we wait for some time for additional information to make a more informed decision. Intuitively, the critical case for our competitiveness is the case where we decide to serve σ L (t) and σ R (t) in a different order than T Opt . Let T RL (t) and T LR (t) be the tours that start at the origin at time 0 and then move as follows,

T RL (t) = waituntil(t R (t) -|a R (t)|) ⊕ move(a R (t)) ⊕ move(a L (t)) ⊕ move(p 0 ), T LR (t) = waituntil(t L (t) -|a L (t)|) ⊕ move(a L (t)) ⊕ move(a R (t)) ⊕ move(p 0 ). Note that |T RL (t)| (resp. |T LR (t)|
) is a lower bound for the length of the shortest tour serving σ R (t) before σ L (t) (resp. σ L (t) before σ R (t)). Say that, at time t, both extremes exist and we greedily decide to immediately start serving the extremes in the same order as T LR (t). To see how this can fail, assume that T Opt initially follows the tour T RL (t), but continues to move to the left after serving σ L (t). The time when

T Opt reaches a L (t) is t = t R (t) + |a R (t)| + |a L (t)|, since t R (t) ≥ |a R (t)| by assumption.
Let t 0 be the time when we reach the origin p 0 after serving σ L (t), and assume that t ≤ t 0 . Now a new request σ = (p ; t 0 ) may arrive at time t 0 and posi-

tion p = -|a L (t)| -(t 0 -t ) = -t 0 + t R (t) + |a R (t)|,
that the optimum can serve immediately at time t 0 . We then have

|T Opt | = t 0 + |p | = t 0 + |a L (t)| + (t 0 -t ) = 2t 0 -t R (t) -|a R (t)|.
Our algorithm still needs to serve σ and σ R at time t 0 , and hence

|T Alg | = t 0 + 2|p | + 2|a R (t)| = 3t 0 -2t R (t).
For the algorithm to be ρ-competitive, we need |T Alg |/|T Opt | ≤ ρ, and we thus obtain a condition on the earliest time t 0 we may return to the origin. Fact 3.1. If at time t a ρ-competitive algorithm serves the leftmost extreme σ L (t) first and t 0 denotes the first time the server returns to the origin after having served σ L (t), then

t 0 ≥ t L 0 (t) := ρ|a R (t)| -(2 -ρ)t R (t) 2ρ -3 . (3.1)
A symmetric statement with t R 0 (t) holds if the algorithm serves σ R (t) first. Fact 3.1 illustrates that waiting is sometimes necessary in order to be competitive. On the other hand, we can obviously not afford to wait too long. To quantify this, we introduce a lower bound on the length of T Opt . Definition 3.1. If both extreme request exist at time t we define the greedy tour T greedy (t) at time t as

T greedy (t) := T LR (t), if |T LR (t)| ≤ |T RL (t)|, T RL (t), else.
If only σ L (t) exists, we set T greedy (t) := T LR (t) and we set T greedy (t) := T RL (t) if only σ R (t) exists.

Observation 3.1. We have

|T RL (t)| = t R (t) + |a R (t)| + 2|a L (t)|, |T LR (t)| = t L (t) + |a L (t)| + 2|a
T safe (t) := T wait ⊕ T LR (t), if |a L (t)| ≥ |a R (t)|, T wait ⊕ T RL (t), else,
with

T wait := waituntil(ρ|T greedy (t)| -2|a R (t)| -2|a L (t)|).
We still have to ensure that the definition of T safe (t) is compatible with the requirement from Fact 3.1 regarding the time t 0 when the tour first returns to the origin. In case |a

L (t)| ≥ |a R (t)|, we get t 0 ≥ t L 0 (t) with t 0 = ρ|T greedy (t)| -2|a R (t)| ≥ (4ρ -2)|a R (t)|. Symmetrically, for |a L (t)| < |a R (t)|, we get (4ρ -2)|a L (t)| ≥ t R 0 (t).
In either case, we can derive the following condition on ρ. .

We are now ready to describe our algorithm (cf. Algorithm 1). We argued that it is a safe option to follow T safe (t) in order to stay ρ-competitive, provided no further requests appear. It will turn out that it is indeed always good enough to follow T safe (t), if possible. However, at time t, we may be too far from the extreme that T safe (t) serves first in order to catch up with the safe tour, in which case we have to resort to secondary strategies. If at time t the server cannot reach T safe (t), it instead bases its behavior on the greedy tour as an estimate for T Opt . Surprisingly, this estimate turns out to be sufficient to obtain an optimal online algorithm. There are three situations that can occur if the safe tour cannot be reached at time t. If the online server is on the same side of the origin as the extreme that T greedy (t) serves first, our algorithm decides to follow the greedy tour. If the online server is on the other side of the origin than the extreme that T greedy (t) serves first, we have to ensure that the condition of Fact 3.1 is not violated. If the tour serving the nearer extreme first satisfies (3.1), the algorithm serves this extreme first, i.e., it serves the extremes in a different order than T greedy (t). Otherwise, we can deduce from (3.1) being violated that we can afford to serve the opposite extreme first, i.e., to follow T greedy (t).

T Alg ← waituntil(t wait ) ⊕ move(A) ⊕ move(a) ⊕ move(p 0 ) else if sign(p t ) = sign(a 1 (t)) or t + |p t -a 2 (t)| + |a 2 (t)| < ρ|a1(t)|-(2-ρ)t1 2ρ-3 then (B1,B2) T Alg ← move(a 1 (t)) ⊕ move(a 2 (t)) ⊕ move(p 0 ) else (C) T Alg ← move(a 2 (t)) ⊕ move(a 1 (t)) ⊕ move(p 0 ) end return T Alg Theorem 3.1.
There is a (9 + √ 17)/8 ≈ 1.64competitive algorithm for closed online TSP on the line.

We obtain the main result of this section by analyzing each of the above cases.

Lower Bound for open online TSP

In this section, we consider open online TSP on the line and give a tight lower bound on the best-possible competitive ratio. Note that a lower bound of 2 is obvious: At time 1, we present a request either at -1 or 1, whichever is further away from the online server. The online tour has length at least 2 while the optimum tour has length 1. Remarkably, we are able to show a slightly larger bound that turns out to be tight.

Theorem 4.1. Let ρ ≈ 2.04 be the second-largest root (out of the four real roots) of 9ρ 4 -18ρ 3 -78ρ 2 + 210ρ -107. There is no (ρ -ε)-competitive algorithm for open TSP on the line for any ε > 0.

In the following, we fix any online algorithm Alg and ρ ∈ (2, ρ) and describe an adversarial strategy that forces |T Alg | to be larger than |T Opt | by a factor of at least ρ . After the first request σ R 0 , which is to the right 2 of the origin, we alternatingly present leftmost and rightmost extreme requests, in the i-th iteration called σ L i and σ R i , respectively, depending on Alg's behavior. Roughly, a new leftmost request σ L i appears 2 We assume p 1 ≤ 0; the other case is symmetrical.

whenever the last rightmost request σ R i-1 is served, and a new rightmost request σ R i appears when Alg has moved close enough to σ L i . Importantly, we will show that some pair (σ L i , σ R i ) is critical, in the following sense.

t := (2ρ -2) • |a 1-k | + (ρ -2) • |a k |. (iv) It holds that |a 1-k |/|a k | ≤ 2.
Indeed, we have the following lemma. Lemma 4.1. If there is a request sequence with two critical requests for Alg, we can release additional requests such that Alg is not (ρ -ε)-competitive on the resulting instance.

In the proof, we use the notation from Definition 4.1. We assume that sign(a k ) ≥ 0; the other case is symmetric. For the sake of readability, we define σ L = (a L ; -a L ) := σ 1-k and σ R = (a R ; a R ) := σ k .

Conceptually, we want to present additional requests after |a * 1 | so that Alg serves σ R before σ L . However, it will turn out that serving σ R first is a mistake for Alg, compared with using the tour T LR := move(σ L ) ⊕ move(σ R ). Roughly, we make Opt follow the tour T LR and then let it continue moving to the right until all requests are served by Alg. Accordingly, we will ensure that all additional requests we introduce coincide with Opt's position at their release time.

Assume that we could force Alg to serve σ L immediately after σ R , before serving any additional requests. In this case, we could simply introduce another request at a R at time |T LR |, and, by Definition 4.1 (iii), we would have

|T Alg | ≥ t + 2(|a R | + |a L |) = (2ρ -2) • |a L | + (ρ -2) • |a R | + 2(|a R | + |a L |) = ρ (2|a L | + |a R |) = ρ |T Opt |, (4.2)
as claimed. In general, however, Alg may not serve σ L immediately after σ R , for example by waiting for a while at a R -which forces us to postpone the release of additional requests. Of course, Alg needs to start moving towards σ L at some point to stay competitve if no new requests appear. Our goal is to balance these two effects by introducing one or two new requests.

The additional requests we use depend on the tour that Alg takes after time |a 1 |. Towards this, let t be the earliest possible time that a server starting in a R at time t could serve σ L , that is,

t := t + |a R | + |a L | = (2ρ -2) • |a L | + (ρ -2) • |a R | + |a R | + |a L | = (2ρ -1) • |a L | + (ρ -1) • |a R |.
We characterize the trajectory of Alg at time t ≥ |a 1 | by the difference between t and the earliest possible time that Alg can still serve σ L , if it aborts its tour at time t and takes the shortest tour serving σ R (if needed) and then σ L . Formally, for t ≥ |a 1 |, we define

delay(t) :=              t + 2|a R | + |a L | -p t -t , if σ R not served at t, t + |a L |+p t -t , if σ R served at t but σ L not, undefined, else.
It is easy to see that the following properties hold. Fact 4.1. Consider some t such that delay(t) is defined. Let T be the set of tours that start in position p t at time t and, if Alg has not served σ R at time t, that do not visit a L before a R . The following is true: (i) There is no tour T ∈ T that arrives at a L earlier than t + delay(t). (ii) There is a tour T ∈ T that arrives at a L at time t + delay(t).

The following two lemmata state useful properties of the delay function that will be used to define the additional requests. We will show that if we present an additional request at time |T LR | + W/(ρ -1) (at a distance of W/(ρ -1) to the right of σ R ) and Alg decides to serve σ L before the new request, the ratio between Alg's and Opt's additional costs (Inequality (4.2)) is at least ρ . If Alg can save time by serving the new request first and does so, we need to present yet another request.

It remains to show that we can define a request sequence (depending on Alg) that ends with a pair of critical requests. We use the following strategy:

• W.l.o.g. p 1 ≤ 0. The first request is σ R 0 := (1, 1).

• Whenever, at some time, called t L i in the following, a request at σ R i-1 gets served, we present the new request σ L i := (a L i = -t L i ; t L i ). Based on t L i , we define for t ≥ t L i the two functions

L i (t) := (2ρ -3) • t -(3 -ρ ) • t L i , R i (t) := (4 -ρ ) • t -(2ρ -2) • t L i ,
which can as well be viewed as lines in the pathtime diagram.

• If at some time t R i after t L i Alg crosses L i (t) or R i (t), we present the request σ R i := (a R i = t R i ; t R i ).
• We stop the procedure when one of the following cases occurs. (The pair (σ L i , σ R i ) will be shown to be critical in these cases.)

Case 1: Alg serves σ L i before σ R i if no new requests appear. Case 2: Alg serves σ R i not before time (2ρ -2) • t L i + (ρ -2) • t R i if no new requests appear.
The intuition behind the lines L i and R i is the following: Suppose the position of Alg at t R i is on or to the right of L i and Alg decides to serve σ L i before σ R i in case no new requests appear after t R i . Then the pair (σ L i , σ R i ) satisfies Definition 4.1 (iii). The symmetric statement holds for R i . The following lemma ensures that, in each iteration, we obtain a (non necessarily critical) pair of unserved requests (σ L i , σ R i ) and that Definition 4.1 (iv) is fulfilled.

Lemma 4.4. Let i ≥ 1. At time t L i , Alg is to the right of L i and R i and crosses one of them after t L i and before it serves σ L i . We also have that t R i ≤ 2t L i .

In the proof of Theorem 4.1, we show that Case 1 or 2 eventually occurs, and we formalize the above intuition to show along with Lemma 4.4 that the requests (σ L i , σ R i ) are indeed critical.

Algorithm for open online TSP

In Algorithm 2, we describe an algorithm for the open online TSP on the line which achieves a competitive ratio of ρ ≈ 2.04, matching the lower bound presented in Section 4.

Theorem 5.1. Algorithm 2 is ρ-competitive with ρ ≈ 2.04 being the second-largest root of the polynomial 9ρ 4 -18ρ 3 -78ρ 2 + 210ρ -107.

In the following, we discuss the different cases that can occur in Algorithm 2 and give an intuition of their interplay. Algorithm 2 is called every time a new extreme request is released. It then computes a new tour serving the current extreme requests and thus also all other requests between these extremes. It is important we wait in certain cases to protect against the release of new extremes that force us to serve the extremes in a different order than we initially chose. Algorithm 2 lets the server return to the origin and wait there whenever possible, and moves to the extremes as late as possible. Intuitively, staying as close to the origin as possible has the benefit that the algorithm can delay the choice in which order to serve the extremes for as long as possible. We observe in the lower bound construction (Section 4), that a ρ-competitive algorithm may not serve a request too early, i.e., |p t |/t is bounded when a request is served. The exact bound on this ratio is computed in the proof of Lemma 4.4 and coincides with the bound in Lemma 5.1 for Algorithm 2.

Lemma 5.1. The position of the server in a tour computed by Algorithm 2 satisfies

|p t | t ≤ 3ρ -5 -3ρ 2 + 9ρ -4 ≈ 0.58
for all times t ≥ 0.

We decide the order in which we serve the extremes and possibly wait based on the current position p t of the server, the current time t and the release times and positions of the single or the two extremes. The server always tries to move back to the origin and wait there as long as possible, i.e., it follows the tour T 0 := move(0) ⊕ waituntil(∞) for as long as possible. We use the notation "T 0 . until(condition(τ ))" to denote the tour that follows T 0 until the first time t 0 that satisfies "condition(t 0 )". Note that this may happen before the server reaches the origin.

We now discuss the different cases of the algorithm step-by-step. Let us first consider the simplest case where only one extreme request σ 1 = (a 1 ; t 1 ) is present (cases (P1) and (E1) in Algorithm 2). The offline optimum Opt obviously cannot finish before time t 1 in this case. In order to guarantee ρ-competitiveness it is therefore sufficient to serve σ 1 at time ρt 1 . Hence, we can afford to move to the origin and wait until the equation t + |p t -a 1 | = ρt 1 is satisfied for the current time t and position p t . This ensures that |p t |/t is bounded as stated in Lemma 5.1 (this is not clear and formally proved in the full version of the paper) and that we have the option to change our tour without much additional cost if an extreme on the other side is released later on. We call the resulting tour in this case, the preferred tour (case (P1)). It can happen, however, that we are only able to serve σ 1 later than time ρt 1 , i.e. t + |p t -a 1 | > ρt 1 . This means that the until-condition is already satisfied and the server serves σ 1 immediately. We call this tour the enforced tour (case (E1)). The makespan of Algorithm 2 in this case is |T Alg | = t 1 +|p t1 -a 1 |. But we have |T Opt | ≥ t 1 and also |T Opt | ≥ |p t -a 1 | as Algorithm 2 only visits points on the real line that must also be visited by Opt at some time. Overall, we have

|T Alg | ≤ 2 • Opt, implying ρ-competitiveness.
Now, consider the case where two extremes σ 1 = (a 1 ; t 1 ) and σ 2 = (a 2 ; t 2 ) are present. The two extremes define an interval

[a L (t), a R (t)] = [min{a 1 , a 2 }, max{a 1 , a 2 }].
Note that a L (t) < p t < a R (t) holds by definition of extreme requests.

If 0 / ∈ [a L (t), a R (t)] (case (O) in Algorithm 2), we let σ 1 denote the request closer to the origin, i.e., |a 1 | ≤ |a 2 |. We then immediately serve σ 1 in order to ensure that Lemma 5.1 holds and |p t |/t stays small. We know that the offline optimum Opt cannot finish before time t 2 . After serving σ 1 it is therefore safe to return to the origin and wait as long as we can to reach a 2 at time ρt 2 . We can thus follow the tour T 0 after serving σ 1 at time t + |p t -a 2 | ≥ ρt 2 . Possibly, this equation is already satisfied from the start and

return T 0 . until(τ + |p τ -a 1 | ≥ ρt 1 ) ⊕ move(a 1 ) end if 0 ∈ [a L (t), a R (t)] then (σ 1 = (a 1 ; t 1 ), σ 2 = (a 2 ; t 2 )) ← extremes such that |a 1 | ≤ |a 2 | (O) return move(a 1 ) ⊕ T 0 . until(τ + |p τ -a 2 | ≥ ρt 2 ) ⊕ move(a 2 ) else (σ 1 = (a 1 ; t 1 ), σ 2 = (a 2 ; t 2 )) ← extremes such that t 1 ≤ t 2 if t + |p t -a 1 | ≤ L σ1,σ2 then (P2) return T 0 . until(τ + |p τ -a 1 | = L σ1,σ2 ) ⊕ move(a 1 ) ⊕ move(a 2 ) else if t + |p t -a 2 | ≤ L σ2,σ1 and |a 2 | ≤ 3ρ-5 (2ρ-2)(7-3ρ) (ρt 1 + (ρ -2)|a 1 |) then (A2) return T 0 . until(τ + |p τ -a 2 | = L σ2,σ1 ) ⊕ move(a 2 ) ⊕ move(a 1 ) else (E2)
return move(a 1 ) ⊕ move(a 2 ) end end we serve σ 2 immediately.

Next, consider the case that 0 ∈ [a L (t), a R (t)] (cases (P2), (A2) and (E2)). Let now σ 1 be the request released first, i.e. first, may be closer to σ 2 at the time when this new request appears and now has to go all the way back to the position of a 1 after serving σ 2 . The intuition why it is sufficient to protect against this worst-case is that if σ 1 appears at a position further away from the origin, then this additional distance has to be traveled by Opt as well, and if σ 1 appears closer to the origin, it only benefits our algorithm. In order to ensure ρ-competitiveness in this scenario, the following inequality has to also be satisfied:

t + |p t -a 1 | + 2(|a 1 | + |a 2 |) ≤ ρ(t 2 + |a 1 | + |a 2 |). (5.5) If we now define L σ1,σ2 := min{ρt 1 + (ρ -1)|a 1 | + (ρ -1)|a 2 |, ρt 2 + (ρ -2)|a 1 | + (ρ -2)|a 2 |},
then Inequalities (5.4) and (5.5) are simultaneously satisfied if and only if t + |p t -a 1 | ≤ L σ1,σ2 . If this latter inequality is satisfied with some slack, we again follow the tour T 0 until it becomes tight, so that |p t |/t stays small and we are more flexible to change our tour when new requests appear.

In case the conditions for the preferred tour are not satisfied, we try to serve σ 2 first. This is called the anticipated tour (case (A2)). The inequalities that need to be satisfied in this case are the same as those for the preferred tour with σ 1 and σ 2 exchanged. Moreover, to ensure that |p t |/t is bounded as claimed in Lemma 5.1, the following inequality also needs to be satisfied if Algorithm 2 serves σ 2 first:

|a 2 | ≤ 3ρ -5 (2ρ -2)(7 -3ρ) (ρt 1 + (ρ -2)|a 1 |) ≈ 1.21 • t 1 + 0.02 • |a 1 |.
(5.6)

Intuitively, the inequality ensures that σ 2 is not too far from the origin compared to σ 1 , as otherwise we would need to start too early to serve the extreme σ 2 and would violate the bound on |p t |/t. Lastly, in case neither the conditions for the preferred tour nor the anticipated tour are met, we immediately serve the earlier request σ 1 first and σ 2 directly afterwards. This is called the enforced tour (case (E2)). The main challenge in showing ρcompetitiveness in the analysis of the algorithm is to derive a better lower bound on Opt in this case by considering extremes that must have been released before.

Online Dial-A-Ride on the line

In this section we give a 1 + √ 2 -competitive algorithm for (preemptive) open online Dial-A-Ride on the line. Let T Opt S denote the optimal tour over a set of requests S, starting at position p 0 = 0, and let R t denote the set of released but not yet delivered requests at a time t. Our algorithm works as follows (cf. Algorithm 3): The server stays at position p 0 until the first request arrives. With every new arriving request, the server stops its current tour and returns to p 0 , or stays at p 0 if it is already at the origin. The server starts following the tour T

) ⊕ waituntil( √ 2 • |T Opt Rt |) ⊕ T Opt

Rt

We show that we get back to the origin in time whenever a new request is released. We also provide a lower bound for non-preemptive closed Dial-A-Ride on the line that improves the lower bound of 1.70 from [START_REF] Ascheuer | Online Dial-a-Ride problems: Minimizing the completion time[END_REF]. Theorem 6.2. No algorithm for the non-preemptive closed Dial-A-Ride problem on the line with fixed capacity c ≥ 1 has competitive ratio lower than ρ = 1.75.

The offline problem

Psaraftis et al. [START_REF] Harilaos | Routing and scheduling on a shoreline with release times[END_REF] show that open offline TSP on the line with release dates can be solved in quadratic time. For the closed variant they claim that the optimal tour has the structure [21, pp. Here the waiting time at the origin is chosen maximally such that all requests are still served. We contradict this claim by showing that an optimal server tour may need to turn around arbitrarily many times.

Theorem 7.1. For every k ∈ N, there is an instance of closed TSP on the line such that any optimal solution turns around at least 2k times.

Next, we show a dynamic program that solves closed offline TSP on the line in quadratic time. It is inspired by the one of Psaraftis et al. [START_REF] Harilaos | Routing and scheduling on a shoreline with release times[END_REF] for the open variant and a dynamic program of Tsitsiklis [START_REF] Tsitsiklis | Special cases of traveling salesman and repairman problems with time windows[END_REF] for the same problem with deadlines instead of release times.

The algorithm (cf. Algorithm 4) relies on the fact that an optimal server tour has a 'zig-zag shape' with decreasing amplitude.

We index the requests by increasing positions. Then we compute for each index pair i < j the completion time of two tours serving all requests to positions smaller than position a i and all requests to positions larger than position a j . We use C + i,j for the best such tour ending at position a j and C - i,j for the best one ending at a i . Starting with the largest difference j -i and iteratively decreasing it, we recursively compute C + i,j and C - i,j .

Theorem 7.2. Algorithm 4 computes the minimum completion time of a server tour for offline TSP on the line in time O(n 2 ).

For the non-preemptive Dial-A-Ride problem on the line we show that the open and closed variant with release times are NP-hard. Without release times, we prove they are NP-hard for capacity c ≥ 2. Our reductions are from the circular arc coloring problem, which is also used in a reduction for minimizing the sum of completion times of Dial-A-Ride on the line with capacity c = 1 [START_REF] De Paepe | Computer-aided complexity classification of Dial-a-Ride problems[END_REF].

Algorithm 4: Dynamic Program for Closed Offline TSP on the line. Input: A set of requests σ i = (a i ; t i ) with t i ≥ |a i | for -≤ i ≤ r and a i < a i+1 for -≤ i < r. Output: The minimum completion time C max of a tour. C + --1,r ← t r . C - -,r+1 ← t -. for i = -, ..., r do C - i,r+1 ← max{t i , C - i-1,r+1 + a i -a i-1 }. end for j = r, .., do C + --1,j ← max{t j , C + -1,j+1 + a j+1 -a j }. end for d = r + , ..., 0 do for i = -, .., r -d do j ← i + d. C - i,j ← max{t i , min{C + i-1,j + a j -a i , C - i-1,j + a i -a i-1 }}. C + i,j ← max{t j , min{C + i,j+1 + a j+1 -a j , C - i,j+1 + a j -a i }}. end end return C max = C + 0,0 . In the classification of closed dial-a-ride problems in [START_REF] De Paepe | Computer-aided complexity classification of Dial-a-Ride problems[END_REF], offline TSP on the line is the problem 1|s = t, d j |line|C max . De Paepe et al. [START_REF] De Paepe | Computer-aided complexity classification of Dial-a-Ride problems[END_REF] claim Tsitsiklis [START_REF] Tsitsiklis | Special cases of traveling salesman and repairman problems with time windows[END_REF] shows a polynomial algorithm, but this is for the open version. We solve the closed variant by giving a polynomial algorithm (Theorem 7.2) as well as a counterexample to the algorithm of Psaraftis et al. [START_REF] Harilaos | Routing and scheduling on a shoreline with release times[END_REF]. Our Theorem 7.3 shows the problem 1, cap1|d j |line|C max in the same classification scheme is NP-hard. While this is implicitly claimed in [START_REF] De Paepe | Computer-aided complexity classification of Dial-a-Ride problems[END_REF], no proof is given. For the generalization to arbitrary capacity but without release dates, 1||C max , Guan [START_REF] Jiun | Routing a vehicle of capacity greater than one[END_REF] showed hardness for capacity c = 2 and our new hardness proof handles any capacity c ≥ 2.

  If the tour ends at p 0 = 0, we call it closed, otherwise it is open. We denote the makespan of the tour T by |T |. The objective in the open (closed) version of both TSP and Dial-A-Ride is to find an open (closed) tour T that serves all requests and minimizes |T |.

Fact 3 . 2 .

 32 The safe tour T safe (t) fulfills inequality (3.1) in Fact 3.1 if and only if 2 ≥ ρ ≥ 9+ √ 17 8

Algorithm

Definition 4 . 1 .

 41 We call the last two requests σ 0 = (a 0 ; |a 0 |) and σ 1 = (a 1 ; |a 1 |) of a request sequence with sign(a 0 ) = sign(a 1 ) and 0 < |a 0 | ≤ |a 1 | critical for Alg if the following conditions hold: (i) Both tours move(a 0 )⊕move(a 1 ) and move(a 1 )⊕ move(a 0 ) serve all the requests presented until time |a 1 |. (ii) Alg serves both σ 0 and σ 1 after time |a 1 |, and p |a 1 | lies between a 0 and a 1 . (iii) Let k ∈ {0, 1} be such that Alg serves σ k before σ 1-k . Then Alg serves σ k no earlier than

Lemma 4 . 2 .Lemma 4 . 3 .

 4243 There exists W ≥ 0 with(4.3) delay |T LR | + W ρ -1 = W. With W as in Lemma 4.2, Alg serves σ R no later than time |T LR | + W ρ -1 .

Algorithm 2 :

 2 For the open online TSP problem on the line. This function is called every time a new extreme request is released. Input: Current time t, current extremes, current position p t Output: The next part of the tour for the server T 0 := move(0) ⊕ waituntil(∞) if ∃ only single extreme σ 1 = (a 1 ; t 1 ) then (P1) (E1) (P1),(E1)

Theorem 6 . 1 .√ 2 )Note 6 . 1 .

 61261 Algorithm 3 is (1 + ≈ 2.41competitive for the preemptive open online Dial-A-Ride problem with capacity c ≥ 1. Algorithm 3 can easily be modified to solve open Dial-A-Ride in general metric spaces and upholds the same competitive ratio. The proof remains the same.

  [215][216]:waituntil() ⊕ move(A R ) ⊕ move(A L ) ⊕ move(p 0 ) or waituntil() ⊕ move(A L ) ⊕ move(A R ) ⊕ move(p 0 ).

Theorem 7 . 3 .

 73 The non-preemptive open and closed offline Dial-A-Ride problem on the line are NPcomplete. For capacity c ≥ 2 this even holds when all release times are 0.

Table 1 :

 1 Overview of our results for online TSP on the line and online Dial-A-Ride on the line.

	Online	lower bound	closed	upper bound	lower bound	open	upper bound
	online TSP on the line
	new old	1.64 [5, 6]	1.64 (Th. 3.1) 1.75 [5, 6]	2.04 (Th. 4.1) 2 [4, 6]	2.04 (Th. 5.1) 2.33 [4, 6]
	Dial-A-Ride on the line
	preemptive non-preemptive 1.75 (Th. 6.2) 1.64 [5, 6]	2 [2]	2.04 (Th. 4.1)	2.41 (Th. 6.1) 3.41 [15]

Table 2 :

 2 Overview of our results for offline TSP and Dial-A-Ride on the line with release times.

	Offline	closed	open
	TSP on the line	O(n 2 ) (Th. 7.2)	O(n 2 ) [21]
	Dial-A-Ride on the line
	non-preemptive	NP-hard (Th. 7.3)	NP-hard (Th. 7.3)
	different algorithms for the same setting and present a
	2-competitive algorithm for any finite capacity c ≥ 1.

  Assume we are still waiting at the origin at time t, i.e. p t = 0. From Observation 3.1, we conclude that if t ≤ ρ|T greedy (t)| -2|a R (t)| -2|a L (t)|, we can wait until time ρ|T greedy (t)| -2|a R (t)| -2|a L (t)|, and then still serve σ R (t) and σ L (t) and return to the origin p 0 until time ρ|T greedy | ≤ ρ|T Opt |, i.e., we can stay ρ-competitive. Formally, we make the following definition. Definition 3.2. Let the safe tour T safe (t) at time t be defined as

R (t)| and |T greedy (t)| = min{|T LR (t)|, |T RL (t)|} ≤ |T Opt | if both extremes exist at time t.

  1: Update(t, σ L (t), σ R (t), p t ) for the closed online TSP Problem this function is called upon release of a new extreme request Input: time t, unserved extreme requests σ R (t) and σ L (t), position p t of the server Output: closed Online TSP tour serving all unserved requests A ← argmax g∈{a R (t),a L (t)} |g|; a ← argmin g∈{a R (t),a L (t)} |g| if T greedy (t) = T LR (t) then (a 1 (t); t 1 ) ← σ L (t); (a 2 (t); t 2 ) ← σ R (t) else (a 1 (t); t 1 ) ← σ R (t); (a 2 (t), t 2 ) ← σ L (t) end if t wait := ρ|T greedy (t)| -(|p t -A| + |A| + 2|a|) ≥ t then // T safe (t) can be reached

	(A)

  t 1 ≤ t 2 , and t = t 2 be the current time. We have a lower bound of |T OPT | ≥ t 1 + |a 1 | + |a 2 |, irrespective of whether Opt serves σ 1 or σ 2 first. If we serve σ 1 first, which we call the preferred tour (case (P2)), we ensure that the tour produced by Algorithm 2 is not longer than ρ|T Opt | by satisfying the inequality t + |p t -a 1 | + |a 1 | + |a 2 | ≤ ρ(t 1 + |a 1 | + |a 2 |). (5.4) Now assume that Opt serves σ 2 first and a new request σ 1 = (a 1 ; t 2 + |a 1 | + |a 2 |) appears at the same position as σ 1 when Opt arrives there. The new request does not increase the cost for Opt, which is still only lower bounded by |T OPT | ≥ t 2 + |a 1 | + |a 2 |. But our algorithm, which served σ 1

  By "unload" we denote the operation of unloading all requests the server is currently carrying at the current position. Formally, each such request (a, b; t ) is changed to (p t , b; t ). Output: an open tour starting at p t and serving all requests in R t return unload ⊕ move(p 0

	Opt Rt Rt |. Algorithm 3: For the open online Dial-A-time √ 2 • |T Opt	at
	Ride problem with c ≥ 0 fixed.
	this function is called upon receiving a new
	request;
	Input: new request σ, current position p t ,
	unserved requests R t

Parts of our results were already claimed in[START_REF] Lipmann | On-Line Rounting[END_REF], but mostly with weaker bounds and without a conclusive proof. Nevertheless, some of our ideas are inspired by the approaches described in[START_REF] Lipmann | On-Line Rounting[END_REF].

† Supported by Einstein Foundation Berlin in the framework of Matheon. § Supported by DFG Priority Programme 1736 Algorithms for Big Data. ¶ TU Braunschweig, Institute for * * Supported by Einstein Foundation Berlin in the framework of Matheon and by the German Science Foundation (DFG) under contract ME 3825/1. † † Universidad de Chile, Santiago, Chile. ‡ ‡ Partially supported by the Millennium Nucleus Information and Coordination in Networks ICM/FIC RC130003. § § Vrije Universiteit, Department of Econometrics and Operations Research & CWI,