Sorbonne Université, CNRS, LIP6, F-75005 Paris,
Franceevripidis.bampis@lip6.frhttps://orcid.org/0000-0002-4498-3040 Sorbonne
Université, CNRS, LIP6, F-75005 Paris, France and Institut Universitaire de
France, Paris,
Francebruno.escoffier@lip6.frhttps://orcid.org/0000-0002-6477-8706 National
University of Singapore, Singapore,
Singaporetgoule@nus.edu.sghttps://orcid.org/0000-0002-4056-0489 Sorbonne
Université, CNRS, LIP6, F-75005 Paris,
Franceniklas.hahn@lip6.frhttps://orcid.org/0000-0002-4929-0542 ETH Zürich,
Zürich, Switzerlandklakis@student.ethz.chhttps://orcid.org/0009-0004-5595-1839
Max-Planck-Institut für Informatik, Universität des Saarlandes, Saarbrücken,
Germanygshahkar@mpi-inf.mpg.dehttps://orcid.org/0000-0002-6169-7337 Sorbonne
Université, CNRS, LIP6, F-75005 Paris,
Francemichail.xefteris@lip6.frhttps://orcid.org/0009-0006-2894-3029 Evripidis
Bampis, Bruno Escoffier, Themis Gouleakis, Niklas Hahn, Kostas Lakis, Golnoosh
Shahkarami, and Michalis Xefteris [500]Theory of computation Design and
analysis of algorithms This work was partially funded by the grant
ANR-19-CE48-0016 from the French National Research Agency (ANR).

###### Acknowledgements.

# Learning-Augmented Online TSP on Rings, Trees, Flowers and (almost)
Everywhere Else

Evripidis Bampis  Bruno Escoffier  Themis Gouleakis  Niklas Hahn  Kostas Lakis
Golnoosh Shahkarami  Michalis Xefteris

###### Abstract

We study the Online Traveling Salesperson Problem (OLTSP) with predictions. In
OLTSP, a sequence of initially unknown requests arrive over time at points
(locations) of a metric space. The goal is, starting from a particular point
of the metric space (the origin), to serve all these requests while minimizing
the total time spent. The server moves with unit speed or is “waiting” (zero
speed) at some location. We consider two variants: in the open variant, the
goal is achieved when the last request is served. In the closed one, the
server additionally has to return to the origin. We adopt a prediction model,
introduced for OLTSP on the line [23], in which the predictions correspond to
the locations of the requests and extend it to more general metric spaces.

We first propose an oracle-based algorithmic framework, inspired by previous
work [13]. This framework allows us to design online algorithms for general
metric spaces that provide competitive ratio guarantees which, given perfect
predictions, beat the best possible classical guarantee (_consistency_).
Moreover, they degrade gracefully along with the increase in error
(_smoothness_), but always within a constant factor of the best known
competitive ratio in the classical case (_robustness_).

Having reduced the problem to designing suitable efficient oracles, we
describe how to achieve this for general metric spaces as well as specific
metric spaces (rings, trees and flowers), the resulting algorithms being
tractable in the latter case. The consistency guarantees of our algorithms are
tight in almost all cases, and their smoothness guarantees only suffer a
linear dependency on the error, which we show is necessary. Finally, we
provide robustness guarantees improving previous results.

###### keywords:

TSP, online algorithms, predictions, competitive analysis

###### category:

##  1 Introduction

In the classical Traveling Salesperson Problem (TSP), we are given a set of
locations as well as the pairwise distances between them and the objective is
to find a shortest tour visiting all the locations. TSP is one of the most
fundamental and well studied problems in Computer Science [30]. We focus on
the online version of the problem in a metric space, the Online Traveling
Salesperson Problem (OLTSP), introduced in the seminal paper of Ausiello et
al. [10]. In OLTSP, the input arrives over time, i.e., new requests
(locations) that have to be visited by the traveler (or server) will appear
during the travel. The time in which a request is communicated to the traveler
is called its release time (or release date). The objective is the
minimization of the total traveled time assuming that at any time the traveler
either moves at unit speed or is “waiting” (zero speed) at some
location111Note that this choice of possible speeds is w.l.o.g., as any
setting where the maximum speed is bounded can be reduced to this setting.
Specifically, if the maximum speed is some $S>0$, we can normalize the maximum
speed to be $1$ and multiply all distances by $S$. Also, our setting can
simulate any other setting where the algorithm is free to chose either the
unit speed of some other speed $0<s<1$. Moving at speed $s$ is equivalent to
dividing the time into intervals of length $dt\rightarrow 0$ and moving at
unit speed only for time $s\cdot dt$ within each interval.. We study both the
closed variant, where the server is required to return to the origin after
serving all requests, and the open variant, where the server does not have to
return to the origin after serving all the requests. A series of papers
considered many variations of OLTSP in different metric spaces (general metric
space [10, 13], the line [10, 17, 23], the semi-line [9, 13, 18], the ring
[13, 27] and the star [13]).

The motivation of studying OLTSP and its variations comes from applications in
many different domains, such as e.g. logistics and robotics [8, 37]. In the
framework of competitive analysis, the performance of an online algorithm is
usually evaluated using the competitive ratio which is defined as the maximum
ratio between the cost of the online algorithm and the cost of an optimal
offline algorithm, which by definition has knowledge of the entire input in
advance, over all input instances. However, it is admitted that the
competitive analysis approach can be overly pessimistic as it is calculated
considering worst-case instances, giving a lot of power to the adversary.
Hence, many papers try to limit the power of the adversary [18], or give extra
knowledge and hence more power to the online algorithm [1, 13, 26].

More recently, the framework of Learning-Augmented (LA) algorithms has emerged
due to the vibrant successes of Machine Learning methods and Artificial
Intelligence in predicting and learning the unknown (i.e., future inputs in
the case of online algorithms) based on data [32]. In this line of research,
the goal is to utilize predictions of the future input that have potentially
been acquired using a learning algorithm, in order to have provably improved
competitive ratio in the case that the predictions are accurate enough, while
maintaining worst-case guarantees even if the prediction error is arbitrarily
large. In particular, a (possibly erroneous) prediction of the input is given
to the algorithm and the goal is to design algorithms with a good performance
guarantee when the prediction is accurate (consistency), a not too bad (and
bounded) performance when the prediction is wrong (robustness) and a gradual
deterioration of the competitive ratio with respect to the prediction error
(smoothness). We give more precise definitions in Section 2.

Recent works have proposed a variety of approaches to tackle OLTSP with
predictions (LA-OLTSP). In [23], Gouleakis et al. studied a learning-augmented
framework for OLTSP on the line. They introduced a prediction model in which
the predictions correspond to the locations of the requests. They proposed LA
algorithms for both the closed and the open variants that are consistent,
smooth and robust. Bampis et al., in [13], considered the case of perfect
predictions of the locations and studied different metric spaces (general
metric space, semi-line, ring, and star) and proposed competitive online
algorithms and lower bounds. In [25], Hu et al. proposed three different
prediction models for OLTSP. In two of their models, each request is
associated to a prediction for both its release time and its location while in
the third one the prediction is just the release time of the last request. In
[16], Bernardini et al. studied OLTSP with predictions of both the release
time and the location of each request. They introduced a new error measure,
the cover error, and they also considered other online graph problems. More
recently, Chawla and Christou [19] studied the Online Time-Windows TSP with
predictions of release time and location of the requests.

In this work, we adopt the prediction model of [23]. We propose a general
oracle-based framework that allows us to design consistent, smooth and robust
LA algorithms for both the closed and open variants of the problem for
different metric spaces. We also provide some interesting lower bounds.

###  1.1 Our contributions and techniques

In this paper, we propose a novel approach to improve the competitive ratio of
OLTSP using predictions concerning the locations of requests in general metric
spaces. Our algorithms provide tight competitive ratio guarantees in most
cases. Moreover, we show how to get polynomial-time/FPT algorithms in specific
metrics, namely rings, trees and flowers.

Bampis et al. [13] gave an algorithm for general metrics with a competitive
ratio of $3/2$ for the case of perfect predictions (known locations), which is
tight. First, in Section 3, we modify this algorithm (still under the
assumption of perfect predictions) and introduce our main oracle-based
3/2-competitive framework, which we call _Strategically Wait And Go_ (SWAG,
for pseudocode see Algorithm 1). The main idea is to consider a suitable
subset of permutations of the requests, referred to as _Dominating
permutations_, given by a so-called _Domination oracle_ instead of all the
permutations. This allows for a reduction of the running time, since the
bottleneck is located in the cardinality of the set of considered
permutations. This restriction of the permutation set preserves the
consistency of $3/2$.

Then, we introduce our main algorithm, _Learning-Augmented Strategically Wait
And Go_ (LA-SWAG, for pseudocode see Algorithm 2), which does not assume
perfect predictions. LA-SWAG is consistent, smooth, and robust. More formally,
in Section 4 we show the following.

######  Theorem 1.1 (Consistency and Smoothness).

LA-SWAG has a competitive ratio of at most $3/2+5\eta$ for both closed and
open LA-OLTSP.

Here, $\eta$ is the error of the prediction (defined formally later) that
captures the normalized sum of distances between predicted and actual
locations of the requests. Note that for $\eta=0$, we get a consistency of
$3/2$, which is tight for all cases except the open variant on trees.

Additionally, we show a smoothness lower bound of $3/2+\eta/2$ for the open
variant with $\eta\in[0,1/3]$ (Proposition 4.3), implying that a linear
dependency on $\eta$ is required.

Regarding robustness, the algorithm in [23] achieves $3$-robustness on the
line. LA-SWAG improves this bound for general metrics and further so in
specific metrics.

######  Theorem 1.2 (Robustness-Closed).

LA-SWAG is $2.75$-robust for closed LA-OLTSP in general metric spaces, and
$2.5$-robust in Euclidean spaces and in trees.

######  Theorem 1.3 (Robustness-Open).

LA-SWAG is $\left(3-1/6\right)$-robust for open LA-OLTSP in general metric
spaces, and $\left(3-1/3\right)$-robust in trees.

Our analysis for $2.5$-robustness and $\left(3-1/3\right)$-robustness is tight
even on the line (Remarks 4.10 and 4.15). Moreover, we show a negative result
concerning the consistency/robustness trade-off of any algorithm for the open
variant (Lemma 4.16).

The main technical contribution of our work, found in Sections 5 and 6, is the
implementation of the domination oracles we have referred to. On a high level,
we say that a permutation $\pi_{dom}$ dominates another permutation $\pi$ at
time $t$, if the following conditions hold. Assuming $q$ is the first
unreleased request in $\pi$ at time $t$, the distance traveled up to $q$ is
not longer in $\pi_{dom}$, and also a superset of the requests preceding $q$
in $\pi$ is visited before $q$. Moreover, $\pi_{dom}$ induces a not longer
path than $\pi$. These two key facts allow us to preserve $3/2$-consistency.

For general metrics, we achieve this domination using a very similar idea as
the one employed in the definition of the $O(n^{2}2^{n})$ dynamic programming
solution of the classical TSP [15, 24]. That is, for any possible subset of
released requests that might have been served by $\pi$ before $q$, we simply
build two optimal paths for the parts before and after $q$ (without release
times) and then we concatenate them to get a dominating permutation. We call
the resulting sets general dominating sets. Any permutation is dominated by
the one corresponding to the correct guess of requests served up to $q$. This
yields a single-exponential time algorithm overall.

######  Theorem 1.4 (General Metrics).

LA-SWAG with an oracle $\mathcal{D}$ which uses the general dominating sets
runs in single-exponential time and is $\min\\{3/2+5\eta,2.75\\}$-competitive
for the closed variant and $\min\\{3/2+5\eta,3-1/6\\}$-competitive for the
open variant of LA-OLTSP.

The overarching insight behind how we reduce the runtime in specific metrics
is the fact that we do not really need to try all possible subsets of requests
served before $q$. For example, in trees, we first show a structural result
about the optimal solutions (with release times). Specifically, we prove that
the requests placed along a path from a leaf to the origin (considered the
root) can be assumed to be served in a very specific order. This is the order
in which the requests are encountered as one traverses the path from the leaf
to the origin. This fact allows us to design a domination oracle which,
roughly, provides a single permutation for any subset of leaves visited before
$q$. Hence, we get an FPT algorithm parameterized by the number $l$ of leaves
of the tree.

######  Theorem 1.5 (Trees).

There exists a Domination oracle for LA-SWAG in trees which yields a time
complexity of $O(2^{l}\cdot n^{3})$ for the closed variant and $O(2^{l}\cdot
n^{4})$ for the open variant, where $l$ is the number of leaves of the input
tree.

As a first step towards more general graphs, we deal with the concept of
cycles by considering the ring. While we cannot retrieve the exact same
structural result about online optimal solutions, we show something quite
similar. Namely, we prove that the cyclic nature of the ring may be utilized
only once by an optimal solution. After such a cyclic traversal, we can assume
that the ring is split in half, yielding a tree which we know how to deal
with.

######  Theorem 1.6 (Ring).

There exists a Domination oracle for LA-SWAG in the ring which yields a time
complexity of $O(n^{3})$ for the closed variant and $O(n^{5})$ for the open
variant.

Finally, we combine the two previous sets of ideas to tackle flowers. Flowers
are essentially comprised of a bunch of rings (petals) and a semi-line (stem),
all of which are attached to the origin. It is still true that each single
ring may be assumed to be traversed with a loop only once in this case. It
turns out that we can consider at most $6$ options for every petal.

######  Theorem 1.7 (Flowers).

There exists a Domination oracle for LA-SWAG in flowers which yields a time
complexity of $O(6^{p}\cdot n^{3})$ for the closed variant and $O(6^{p}\cdot
n^{5})$ for the open variant, where $p$ is the number of petals of the input
flower.

We summarize our results in Tables 1 and 2. In the closed variant, there is a
lower bound of $3/2$ even in the case of a line [23]. In the open one, we show
a lower bound of $\approx 1.468$ even in the case of a line in the Appendix
(Proposition A.1) and there is a lower bound of $3/2$ even in the case of a
ring [13].

Table 1: Consistency, smoothness, robustness and runtime guarantees of LA-SWAG. |  | Smoothness
---
(Consistency for $\eta=0$)
Robustness | Runtime
Closed/Open | Closed | Open | Closed | Open
Tree | $3/2+5\eta$ | 2.5 | $3-1/3$ | $O(2^{l}\cdot n^{3})$ | $O(2^{l}\cdot n^{4})$
Ring | 2.75 | $3-1/6$ | $O(n^{3})$ | $O(n^{5})$
Flower | 2.75 | $3-1/6$ | $O(6^{p}\cdot n^{3})$ | $O(6^{p}\cdot n^{5})$
Euclidean | 2.5 | $3-1/6$ | $O(n^{2}\cdot 2^{n})$ | $O(n^{2}\cdot 2^{n})$
General | 2.75 | $3-1/6$ | $O(n^{2}\cdot 2^{n})$ | $O(n^{2}\cdot 2^{n})$
Table 2: Consistency of LA-SWAG and other tractable algorithms. The upper bounds with * are given by an FPT algorithm and a polytime algorithm otherwise. Tight bounds are denoted in bold. |  | Consistency
---
Closed | Open
Previous work | This paper | Previous work | This paper
Line |  | $\boldsymbol{3/2}$ | [23] | $\boldsymbol{3/2\phantom{{}^{*}}}$ |  | 5/3 | [23] | $3/2\phantom{{}^{*}}$
Star |  | 7/4+$\epsilon$ | [13] | $\boldsymbol{3/2^{*}}$ |  | 2 | [13] | $3/2^{*}$
Tree |  | 2 | [10] | $\boldsymbol{3/2^{*}}$ |  | 2 | [13] | $3/2^{*}$
Ring |  | 5/3 | [13] | $\boldsymbol{3/2\phantom{{}^{*}}}$ |  | 2 | [13] | $\boldsymbol{3/2\phantom{{}^{*}}}$
Flower |  | 2 | [10] | $\boldsymbol{3/2^{*}}$ |  | 2 | [13] | $\boldsymbol{3/2^{*}}$

###  1.2 Further related works

The offline version of the problem, in which the locations and release times
are known in advance, has been studied in [17, 37] for both closed and open
variants. For OLTSP, a 2-competitive algorithm for the closed variant and a
2.5-competitive algorithm for the open variant have been proposed in general
metric spaces by [10]. Specifically on the line, there exist lower bounds of
$1.64$ [10] and $2.04$ [17] for the closed and open variants, respectively.

In addition to online TSP, there are several works that have explored learning
augmented settings. The online caching problem with predictions was
investigated by [32], and the initial results were improved by [3, 39, 41].
Adopting the LA approach, algorithms were developed for the ski-rental problem
[2, 22, 38, 40] as well as for scheduling problems [4, 11, 34, 36]. There is
also literature on learning augmented algorithms for classical data structures
[29], bloom filters [33], routing problems [14, 21, 28], online selection and
matching problems [5, 20] and a more general framework of online primal-dual
algorithms [12]. There is a survey [35] and an updated list of papers [31] in
this area.

##  2 Preliminaries

#### Online TSP (OLTSP).

The input of OLTSP consists of a metric space $M$ with a distinguished point
$\mathcal{O}$ (the origin), and a set $Q=\\{q_{1},...,q_{n}\\}$ of $n$
requests. Every request $q_{i}$ is a pair ($x_{i},t_{i}$), where $x_{i}$ is a
point of $M$ and $t_{i}\geq 0$ is a real number. We use $t$ to quantify time.
The number $t_{i}$ represents the moment after which the request $q_{i}$ can
be served (release time). A server located at the origin at time $t=0$, which
can move with unit speed, must serve all the requests after their release
times with the goal of minimizing the total completion time (makespan).

We consider a wide class of continuous metric spaces $M$ whose corresponding
distance metric $d(x,y)$ is defined as the shortest path from $x\in M$ to
$y\in M$ and is continuous in $M$, as in [10]. We call this class general
metric spaces (or general metrics). The release times for continuous metric
spaces can be any non-negative real number.

For the rest of the paper, we denote the total completion time of an online
algorithm by $|$ and that of an optimal (offline) solution
$\operatorname{OPT}$ by $|\operatorname{OPT}|$. We recall that an algorithm is
/-competitive if on all instances we have $|$.

#### Learning-augmented algorithms.

In order to measure the quality of the predictions, we will define a
prediction error $\eta$. LA algorithms have three main properties. We use the
formal definitions in [23] here. We say that an algorithm is

  * •

$\alpha$-consistent, if it is $\alpha$-competitive when $\eta=0$,

  * •

$\beta$-robust, if it is always $\beta$-competitive regardless of $\eta$, and

  * •

$\gamma$-smooth for a continuous function $\gamma(\eta)$, if it is
$\gamma(\eta)$-competitive.

In general, if $c$ is the best competitive ratio achievable without
predictions, it is desirable to have $\alpha<c$, $\beta\leq k\cdot c$ for some
constant $k$ and also the function $\gamma$ should increase from $\alpha$ to
$\beta$ along with the error $\eta$.

#### Our prediction setting.

Let $Q=\\{q_{1},\dots,q_{n}\\}$ be the set of requests. As we mentioned, each
request $q_{i}$ has a corresponding release time $t_{i}$ and a location
$x_{i}$. We have a set of predictions $P=\\{p_{1},\dots,p_{n}\\}$ in which
$p_{i}$ predicts $x_{i}$, the location of request $q_{i}$. The algorithm gets
these predictions as well as the number of requests $n$ as an offline input.
The actual values of $x_{i}$ and $t_{i}$ only become known at time-point
$t_{i}$.

The predictions’ quality can vary and is unknown to the algorithm. We can
evaluate the quality by defining a measure $\eta$. Essentially, $\eta$
measures the sum of all the distance between the predicted location and the
actual ones normalized by the length of a shortest path serving all the
requests.

######  Definition 2.1 (Prediction Error).

The prediction error of an instance is defined by
$\eta=\frac{\sum_{i=1}^{n}d(x_{i},p_{i})}{F}$, where $F$ is the length of a
shortest path serving all the requests (and returning to the origin in the
closed case).

Note that the prediction error is scale invariant (i.e., it will not change if
all the distances are multiplied by a constant factor), and $F$ acts as the
normalization factor.

##  3 Oracle-based framework: the SWAG algorithm

In this section, we define an oracle-based algorithm, SWAG, designed for the
case of perfect predictions. The oracle provides the algorithm with a set of
permutations of the requests. We show that if the oracle satisfies some
conditions, then SWAG has a competitive ratio of 3/2.

SWAG is actually a (slightly) modified version of the general algorithm in
[13]. The principle of this latter algorithm is the following:

  * •

First, to wait at $\mathcal{O}$ until a chosen time $T$. This time $T$ depends
both on the requests’ locations and on their release times.

  * •

Then, to choose a route of serving requests that minimizes some criterion
involving the length of the corresponding route and the fraction of it which
is released at time $T$, and to follow this route, waiting at unreleased
requests.

The calculation of the chosen time $T$ on the first step is done by computing
some values on all the $n!$ permutations of the requests. The improvement we
show here is that we can get the same competitive ratio (i.e., 3/2) while
considering not the whole set of permutations, but some well chosen (and
ideally small) subset that satisfies a certain property. This subset of
permutations is given to the algorithm by the oracle.

Then, based on this framework, to derive an efficient 3/2-competitive
algorithm, one only has to build an efficient oracle. We will show for example
in Section 6 that for lines or rings, we can devise a polytime oracle building
a polysize subset of permutations, leading to a polytime 3/2-competitive
algorithm for these metrics.

More formally, we consider SWAG, which uses the following notation. For a
given order $\sigma$ on the requests (where $\sigma[i]$ denotes the $i$-th
request in the order), we denote:

  * •

by $\ell_{\sigma}$ the length of the route associated to $\sigma$ (starting at
$\mathcal{O}$), i.e.,
$\ell_{\sigma}=d(\mathcal{O},\sigma[1])+\sum_{j=1}^{n-1}d(\sigma[j],\sigma[j+1])$
in the open case,
$\ell_{\sigma}=d(O,\sigma[1])+\sum_{j=1}^{n-1}d(\sigma[j],\sigma[j+1])+d(\sigma[n],\mathcal{O})$
in the closed case;

  * •

by $\alpha_{\sigma}(t)$ the fraction of the length of the largest fully
released prefix of the route associated to $\sigma$ at time $t$ over
$\ell_{\sigma}$. More formally, if all $n$ requests are released, then
$\alpha_{\sigma}(t)=1$ for all $\sigma$, otherwise, if requests
$\sigma[1],\dots,\sigma[k-1]$ are released at $t$ but $\sigma[k]$ is not, then
the route is fully released up to $\sigma[k]$, and

$\alpha_{\sigma}(t)={\big{(}d(\mathcal{O},\sigma[1])+\sum_{j=1}^{k-1}d(\sigma[j],\sigma[j+1])}\big{)}/{\ell_{\sigma}}\enspace.$

Note that this definition requires $\ell_{\sigma}>0$. If $\ell_{\sigma}=0$,
i.e., all requests are at $\mathcal{O}$, we set $\alpha_{\sigma}=1$.

Input: Offline: request locations $x_{1},\dots,x_{n}$

Input: Online: release times $t_{1},\dots,t_{n}$

Input: Parameter: an oracle $\mathcal{D}$ which outputs a set of permutations
on requests

1 Call the oracle $\mathcal{D}$ to get an initial set $S(0)$ of permutations
at $t=0$. Set $S=S(0)$.

2 while  _true_ do

3 At each release time $t_{i}$, request a new set $S(t_{i})$ of permutations
and update $S=S(t_{i})$. For every $\sigma\in S$, compute $\ell_{\sigma}$ and
$\alpha_{\sigma}(t_{i})$.

4 If $\exists\>\sigma_{0}\in S$ s.t. (1) $t\geq\ell_{\sigma_{0}}/2$ and (2)
$\alpha_{\sigma_{0}}(t)\geq 1/2$, set $T=t$ and break.

5 end while

At time $T$:

  * 6•

Compute an order $\sigma_{1}$ which minimizes, over all orders
$\sigma^{\prime}\in S$ , $(1-\beta_{\sigma^{\prime}})\ell_{\sigma^{\prime}}$,

where $\beta_{\sigma^{\prime}}=\min\\{\alpha_{\sigma^{\prime}}(T),1/2\\}$.

* 7•

Follow the tour/path associated to $\sigma_{1}$. Serve the requests in this
order,

waiting at a request location if this request is not released.

Algorithm 1 Strategically Wait And Go (SWAG)

The algorithm for general metrics in [13] considers all possible permutations
of requests to find the waiting time $T$ and a good permutation to follow.
With SWAG, we build on this idea. Crucially, at any point in time $t$, it
focuses only on a subset $S$ of permutations to determine $T$ and the
permutation to follow. The key idea behind these subsets is the following. To
achieve the same competitive ratio, it is sufficient that for any possible
permutation $\sigma$, the set $S$ contains a permutation $\sigma^{\prime}$
that induces a tour/path that is not longer than that of $\sigma$, and its
unreleased portion of the tour at time $t$ is not larger than that of
$\sigma$. We will say that $\sigma^{\prime}$ dominates $\sigma$ and define
this notion formally below. Furthermore, since the released parts only change
when a new request is released, it is sufficient to only update the subset in
that case.

######  Definition 3.1 (Dominating permutation).

Let $\sigma$ be a permutation of the $n$ requests and $t$ a given time. We
define Dom($\sigma,t$) to be the set of permutations that dominate permutation
$\sigma$ at time $t$. A permutation $\sigma^{\prime}\in Dom(\sigma,t)$ if and
only if:

$\ell_{\sigma^{\prime}}\leq\ell_{\sigma}\enspace,$ (1)

and

$(1-\alpha_{\sigma^{\prime}}(t))\ell_{\sigma^{\prime}}\leq(1-\alpha_{\sigma}(t))\ell_{\sigma}\enspace.$
(2)

We also say that $\sigma^{\prime}$ is a corresponding dominating permutation
of $\sigma$ (at time $t$).

For ease of exposition, we assume that the subsets of permutations are given
to the algorithm by an oracle $\mathcal{D}$. We will discuss in Sections 5 and
6 how to implement such oracles for specific cases.

We show that SWAG with an oracle $\mathcal{D}$ is $3/2$-consistent if
$\mathcal{D}$ is a _domination oracle_. Formally, we have the following.

######  Definition 3.2 (Domination oracle).

An oracle $\mathcal{D}$ which outputs at time $t$ a set $S(t)$ of permutations
is a domination oracle if

  1. 1.

$S(t)\subseteq S(t^{\prime})$ for every $t\leq t^{\prime}$, and

  2. 2.

for all $t$ there exists a permutation $\sigma^{\prime}\in S(t)$ such that
$\sigma^{\prime}\in\text{Dom}(\sigma_{\operatorname{OPT}},t)$. Here,
$\sigma_{\operatorname{OPT}}$ is the permutation corresponding to the serving
order of requests in an optimal solution.

######  Lemma 3.3.

SWAG is $3/2$-consistent for both closed and open variants of OLTSP with
perfect predictions if it uses a domination oracle.

######  Proof 3.4.

We denote by $S(t)$ the set of permutations that the algorithm considers at
time $t$ (set $S$ in the description of SWAG) and by $t_{q}$ the release time
of a request $q$. Note that the few times we drop the dependence on $t$ we
imply $t=T$.

First, we show that the algorithm always terminates since the while loop in
SWAG always terminates when a domination oracle is used. When all requests
have been released we have that $\alpha_{\sigma}(t)=1$ for every permutation
$\sigma$ of requests. From Equation (2) and the domination oracle’s condition
2 we get that there is $\sigma^{\prime}\in S(t)$ such that
$(1-\alpha_{\sigma^{\prime}}(t))\ell_{\sigma^{\prime}}\leq 0$. Then
$\alpha_{\sigma^{\prime}}(t)=1$ (when $\ell_{\sigma^{\prime}}=0$ we also have
that $\alpha_{\sigma^{\prime}}(t)=1$ from the definition of $\alpha$). So,
there is a time $t^{\prime}$ such that $t^{\prime}=\ell_{\sigma^{\prime}}/2$
and the loop terminates no later than $t=t^{\prime}$.

At time $T$, there exists a permutation $\sigma_{0}\in S(T)$ with
$T\geq\ell_{\sigma_{0}}/2$ and $\alpha_{\sigma_{0}}(T)\geq 1/2$. Then
$\beta_{\sigma_{0}}=1/2$, and
$(1-\beta_{\sigma_{0}})\ell_{\sigma_{0}}=\ell_{\sigma_{0}}/2\leq T$. By
definition of $\sigma_{1}$, we have
$(1-\beta_{\sigma_{1}})\ell_{\sigma_{1}}\leq(1-\beta_{\sigma_{0}})\ell_{\sigma_{0}}$.
So we get

$(1-\beta_{\sigma_{1}})\ell_{\sigma_{1}}\leq T\enspace.$ (3)

Now let us consider the optimal solution $\operatorname{OPT}$ and its
corresponding permutation $\sigma_{\operatorname{OPT}}$. Consider at time $t$
a corresponding dominating permutation of $\operatorname{OPT}$,
$\sigma^{\prime}(t)\in S(t)$ (domination oracle’s condition 2). Since
$\sigma^{\prime}$ will always refer to a permutation that dominates
$\operatorname{OPT}$, we drop the $\operatorname{OPT}$ in the notation. From
Equation (2), it follows that

$|\operatorname{OPT}|\geq
T+(1-\alpha_{\sigma_{\operatorname{OPT}}}(T))\ell_{\sigma_{\operatorname{OPT}}}\geq
T+(1-\alpha_{\sigma^{\prime}(T)}(T))\ell_{\sigma^{\prime}(T)}\enspace.$

We distinguish two cases for the value of $\alpha_{\sigma^{\prime}(T)}(T)$.

If $\alpha_{\sigma^{\prime}(T)}(T)\leq 1/2$, then
$\beta_{\sigma^{\prime}(T)}(T)=\alpha_{\sigma^{\prime}(T)}(T)$, and

$|\operatorname{OPT}|\geq
T+(1-\alpha_{\sigma^{\prime}(T)}(T))\ell_{\sigma^{\prime}(T)}=T+(1-\beta_{\sigma^{\prime}(T)}(T))\ell_{\sigma^{\prime}(T)}\enspace.$

Since $\sigma_{1}$ is a minimizer for $(1-\beta)\ell$ at $T$ we get

$|\operatorname{OPT}|\geq T+(1-\beta_{\sigma_{1}})\ell_{\sigma_{1}}\enspace.$

Otherwise, if $\alpha_{\sigma^{\prime}(T)}(T)>1/2$, then
$\beta_{\sigma^{\prime}(T)}(T)=1/2$. We study two sub-cases.

  * •

Case 1: $T\neq t_{q}$ for every request $q$. Since the algorithm updates set
$S(t)$ only when there is a release of a new request, the corresponding
dominating permutation of $\operatorname{OPT}$, $\sigma^{\prime}(T)$, is the
same at $T-\epsilon^{\prime}$, $\forall\epsilon^{\prime}\in(0,\epsilon_{1}]$
for a sufficiently small $\epsilon_{1}>0$ (we can choose $\epsilon_{1}$ such
that there is no release of a new request in $[T-\epsilon^{\prime},T]$,
$\forall\epsilon^{\prime}\in(0,\epsilon_{1}]$). So, we have that
$\sigma^{\prime}(T)=\sigma^{\prime}(T-\epsilon^{\prime})$,
$\forall\epsilon^{\prime}\in(0,\epsilon_{1}]$.

We now look at the position of $\operatorname{OPT}$ at time $T$ in its route.
Suppose that it is (strictly) on the second half of this route. Then, at
$T-\epsilon$ (for a sufficiently small $\epsilon_{1}\geq\epsilon>0$), it was
already on the second part. But then
$T-\epsilon\geq\ell_{\sigma_{\operatorname{OPT}}}/2$ (as $\operatorname{OPT}$
has already visited half of the route). So, from Equation (1) we get
$T-\epsilon\geq\ell_{\sigma_{\operatorname{OPT}}}/2\geq\ell_{\sigma^{\prime}(T-\epsilon)}/2$.
Moreover, since in $[T-\epsilon,T]$ there is no release of a new request, we
have that
$\alpha_{\sigma^{\prime}(T-\epsilon)}(T-\epsilon)=\alpha_{\sigma^{\prime}(T-\epsilon)}(T)>1/2$.
Then $T-\epsilon$ would satisfy the two conditions for the starting time of
the algorithm, a contradiction with the definition of $T$. Consequently, at
$T$, $\operatorname{OPT}$ is in the first half of its route. So
$|\operatorname{OPT}|\geq T+\ell_{\sigma_{\operatorname{OPT}}}/2\geq
T+\ell_{\sigma^{\prime}(T)}/2=T+(1-\beta_{\sigma^{\prime}(T)}(T))\ell_{\sigma^{\prime}(T)}$.
Since $\sigma_{1}$ is a minimizer for $(1-\beta)\ell$ at $T$, we get
$|\operatorname{OPT}|\geq T+(1-\beta_{\sigma_{1}})\ell_{\sigma_{1}}$.

  * •

Case 2: $T=t_{q}$ for some request $q$. We can now find a (sufficiently small)
$\epsilon_{1}>0$ such that there is no release of a new request in
$[T-\epsilon_{1},T)$. We can then find another (sufficiently small)
$\epsilon_{2}$ with $0<\epsilon_{2}\leq\epsilon_{1}$ such that
$\operatorname{OPT}$ is only in the first half of its route in
$[T-\epsilon_{2},T)$ or only on the second half of its route in
$[T-\epsilon_{2},T)$. Let $\epsilon\in(0,\epsilon_{2}]$. We now look at the
position of $\operatorname{OPT}$ at time $T-\epsilon$ in its route.

    * –

If $\operatorname{OPT}$ is in the first half at $T-\epsilon$, then
$|\operatorname{OPT}|\geq T-\epsilon+\ell_{\sigma_{\operatorname{OPT}}}/2\geq
T-\epsilon+\ell_{\sigma^{\prime}(T)}/2=T-\epsilon+(1-\beta_{\sigma^{\prime}(T)}(T))\ell_{\sigma^{\prime}(T)}$.
The inequality holds for every choice of $\epsilon\in(0,\epsilon_{2}]$, so
taking the limit $\epsilon\to 0$ we get $|\operatorname{OPT}|\geq
T+(1-\beta_{\sigma^{\prime}(T)}(T))\ell_{\sigma^{\prime}(T)}$. Since
$\sigma_{1}$ is a minimizer for $(1-\beta)\ell$ at $T$, we get
$|\operatorname{OPT}|\geq T+(1-\beta_{\sigma_{1}})\ell_{\sigma_{1}}$.

    * –

If $\operatorname{OPT}$ is (strictly) on the second half of its route at
$T-\epsilon$, then consider a corresponding dominating permutation of
$\operatorname{OPT}$ at $T-\epsilon$ that is contained in $S(T-\epsilon)$,
$\sigma^{\prime}(T-\epsilon)$.

Suppose that $\alpha_{\sigma^{\prime}(T-\epsilon)}(T-\epsilon)>1/2$. Then,
since $\operatorname{OPT}$ is (strictly) on the second half at $T-\epsilon$,
we have that $T-\epsilon\geq\ell_{\sigma_{\operatorname{OPT}}}/2$ (as
$\operatorname{OPT}$ has already visited half of the route). So, from Equation
(1) we get
$T-\epsilon\geq\ell_{\sigma_{\operatorname{OPT}}}/2\geq\ell_{\sigma^{\prime}(T-\epsilon)}/2$.
Then $T-\epsilon$ would satisfy the two conditions for the starting time of
the algorithm, a contradiction with the definition of $T$. So, if
$\operatorname{OPT}$ is (strictly) on the second half of its route at
$T-\epsilon$, it holds that
$\alpha_{\sigma^{\prime}(T-\epsilon)}(T-\epsilon)\leq 1/2$.

So, $\alpha_{\sigma^{\prime}(T-\epsilon)}(T-\epsilon)\leq 1/2$ and
$\beta_{\sigma^{\prime}(T-\epsilon)}(T-\epsilon)=\alpha_{\sigma^{\prime}(T-\epsilon)}(T-\epsilon)$.
From Equation (1) we have that

$\displaystyle|\operatorname{OPT}|$ $\displaystyle\geq
T-\epsilon+(1-\alpha_{\sigma_{\operatorname{OPT}}}(T-\epsilon))\ell_{\sigma_{\operatorname{OPT}}}$
$\displaystyle\geq
T-\epsilon+(1-\alpha_{\sigma^{\prime}(T-\epsilon)}(T-\epsilon))\ell_{\sigma^{\prime}(T-\epsilon)}$
$\displaystyle=T-\epsilon+(1-\beta_{\sigma^{\prime}(T-\epsilon)}(T-\epsilon))\ell_{\sigma^{\prime}(T-\epsilon)}\enspace.$

Note that at time $T$ the set $S(T)$ also contains the permutation
$\sigma^{\prime}(T-\epsilon)$ that dominates $\sigma_{\operatorname{OPT}}$ at
$T-\epsilon$ (domination oracle’s condition 1). So,
$\alpha_{\sigma^{\prime}(T-\epsilon)}(T-\epsilon)\leq\alpha_{\sigma^{\prime}(T-\epsilon)}(T)$
and
$\beta_{\sigma^{\prime}(T-\epsilon)}(T-\epsilon)\leq\beta_{\sigma^{\prime}(T-\epsilon)}(T)$,
for every $\epsilon\in(0,\epsilon_{2}]$ ($\alpha$ and $\beta$ are non
decreasing functions of time for a fixed permutation). Thus, we get
$|\operatorname{OPT}|\geq
T-\epsilon+(1-\beta_{\sigma^{\prime}(T-\epsilon)}(T))\ell_{\sigma^{\prime}(T-\epsilon)}$.
This implies $|\operatorname{OPT}|\geq
T-\epsilon+(1-\beta_{\sigma_{1}})\ell_{\sigma_{1}}$ since $\sigma_{1}$ is a
minimizer for $(1-\beta)\ell$ at $T$. As the above inequality holds for every
$\epsilon\in(0,\epsilon_{2}]$, for $\epsilon\to 0$ it follows that
$|\operatorname{OPT}|\geq T+(1-\beta_{\sigma_{1}})\ell_{\sigma_{1}}$.

Consequently, in all cases we have that

$|\operatorname{OPT}|\geq
T+(1-\beta_{\sigma_{1}}(T))\ell_{\sigma_{1}}\enspace.$ (4)

Now we look at the value $|$ of the solution output by the algorithm. We
distinguish two cases:

  * •

If  does not wait after $T$, it holds that $|$. By definition
$\beta_{\sigma_{1}}(T)\leq 1/2$, so $|$. Adding Equations (3) and (4) with
coefficients $1/2$ and $3/2$, we get
$T+2(1-\beta_{\sigma_{1}}(T))\ell_{\sigma_{1}}\leq 3|\operatorname{OPT}|/2$.
Hence, $|$.

  * •

Otherwise,  waits after $T$ for some request to be released. Let $t^{*}$ be
the last time  waits. As a fraction $\alpha_{\sigma_{1}}(T)$ of $\sigma_{1}$
is completely released at $T$ (i.e., when  starts),  has distance at most
$(1-\alpha_{\sigma_{1}}(T))\ell_{\sigma_{1}}$ to perform after $t^{*}$. So

$|$ (5)

where we use the fact that, by definition,
$\beta_{\sigma_{1}}(T)\leq\alpha_{\sigma_{1}}(T)$. We have
$t^{*}\leq|\operatorname{OPT}|$, as a request is released at $t^{*}$. Adding
Equations (3) and (4) gives
$2(1-\beta_{\sigma_{1}}(T))\ell_{\sigma_{1}}\leq|\operatorname{OPT}|.$ Putting
these two inequalities in Equation (5) gives $|$.

Let us consider now the running time of SWAG and prove the following lemma.

######  Lemma 3.5.

If $N$ is the maximum number of permutations which the oracle $\mathcal{D}$
outputs at each time $t$ and $T_{\mathcal{D}}$ is the total time required (by
the oracle) to compute all permutations, then the running time of SWAG is
$O(\max\\{n^{2}\cdot N,T_{\mathcal{D}}\\})$.

######  Proof 3.6.

For every release time $t_{i}$ and every permutation $\sigma\in S(t_{i})$, the
algorithm has to compute the length $\ell_{\sigma}$ and the fraction of the
associated tour that is released, $\alpha_{\sigma}$. It can do that with
$O(n)$ operations and has to repeat this procedure $n+1$ times, once for every
release of a new request (and once at $t=0$). If $N$ is the maximum number of
permutations which the oracle $\mathcal{D}$ outputs, then the total running
time of the algorithm without taking the oracle’s workload into account is
$O(n^{2}\cdot N)$. Moreover, if we assume that for all calls of the oracle
$\mathcal{D}$ the total computational time required by $\mathcal{D}$ to
compute all permutations is $T_{\mathcal{D}}$, then the total running time of
SWAG is $O(\max\\{n^{2}\cdot N,T_{\mathcal{D}}\\})$.

##  4 Performance guarantees for LA-OLTSP: the LA-SWAG algorithm

In this section, we deal with imperfect predictions; more specifically, we
show how to adapt SWAG to also get smoothness and robustness upper bounds. We
first present the algorithm, then the consistency-smoothness analysis, and
finally the robustness analysis.

Input: Offline: predicted request locations $p_{1},\dots,p_{n}$

Input: Online: release times $t_{1},\dots,t_{n}$, true request locations
$x_{1},\dots,x_{n}$

Input: Parameter: an oracle $\mathcal{D}$ which outputs a set of permutations
on requests

1

2

3(Breaking rule) At any time $t$: if all requests are released, follow an
optimal path serving all unserved requests (returning to $\mathcal{O}$ if in
the closed variant) and break.

4

5

6Run SWAG until the starting time $T$ of the server, and the computation of
$\sigma_{1}$.

7

8

9At time $T$, follow the tour/path $\sigma_{1}$, serving the requests in the
following order:

10 for  _$i=1,\dots,n$_ do

11

  * •

first go to $p_{\sigma_{1}[i]}$; if $q_{\sigma_{1}[i]}$ is not released, wait
there until it is released;

  * •

then, go to $x_{\sigma_{1}[i]}$ and serve the request.

12 end for

13In the closed version, go back to $\mathcal{O}$.

Algorithm 2 Learning-Augmented Strategically Wait And Go (LA-SWAG)

We note that if the predictions are perfect, then LA-SWAG is at least as good
as SWAG (it works the same, the only difference being that it optimally serves
the remaining unserved requests when everything is released). So in particular
it is 3/2-consistent as well, provided that the oracle satisfies the
conditions of Lemma 3.3.

We also note that the algorithm could serve the request in a more clever way:
instead of going first to the predicted location of a request and then to its
true location, the algorithm could go to the true location directly if it is
released (or as soon as it is). However, the lower bounds we will provide
still hold under this modification.

Regarding the running time of LA-SWAG, it is trivial to see that if $T_{TSP}$
is the time required for the computation of an optimal path serving a subset
of the requests, then from Lemma 3.5 we get the following.

######  Corollary 4.1.

If $N$ is the maximum number of permutations which the oracle $\mathcal{D}$
outputs at each time $t$, $T_{\mathcal{D}}$ is the total time required (by the
oracle) to compute all permutations and $T_{TSP}$ is the time for the
computation of an optimal path that serves a subset of the requests, then the
running time of LA-SWAG is $O(\max\\{n^{2}\cdot
N,T_{\mathcal{D}},T_{TSP}\\})$.

Note that, for the cases we consider, we achieve suitable bounds on $T_{TSP}$.
We describe how this is this done for each metric space in Section 6.

###  4.1 Smoothness

We now show that LA-SWAG is smooth with respect to the measure of error $\eta$
in the predictions, where we recall that
$\eta={\sum_{i=1}^{n}d(x_{i},p_{i})}/{F}$ with $F$ the length of a shortest
TSP-tour serving all the requests (and returning to the origin in the closed
case), ignoring release times. For convenience, let $\Delta=\eta
F=\sum_{i=1}^{n}d(x_{i},p_{i})$.

See 1.1

######  Proof 4.2.

Let $I$ be an instance of the problem with requests $q_{1},\dots,q_{n}$,
predictions $p_{1},\dots,p_{n}$ and actual locations $x_{1},\dots,x_{n}$. Let
us denote by $I_{H}$ a corresponding (hypothetical) instance of the problem
where the predicted locations $p_{1},\dots,p_{n}$ would be the actual ones (so
$I_{H}$ is an instance with perfect predictions). Let us denote by (resp.
$\operatorname{OPT}_{I_{H}}$) the solution output by SWAG on $I_{H}$ (resp. an
optimal solution on $I_{H}$). By Lemma 3.3, we have $|$ since in $I_{H}$ the
predictions are perfect.

Now, we first claim that $|$. As previously noticed, the breaking rule in LA-
SWAG cannot increase the value of the solution, so $|$ where is the solution
on $I$ that would perform the entire for loop in Step 4 of LA-SWAG. Note that
now and start at the same time $T$, and serve the requests in the same order
$\sigma_{1}$. Let $t^{*}$ be the last time waits on a prediction
$p_{\sigma_{1}[s]}$ for the actual instance $I$, or $t^{*}=T$ if never waits
on a prediction. In the first case, cannot serve the corresponding request
$\sigma_{1}[s]$ before $t^{*}$ (as it is not released). In the second case,
does not leave the origin before $t^{*}$. Thus, denoting for convenience
$s=0$, ${\sigma_{1}[0]}=0$ and $p_{0}=\mathcal{O}$ if never waits at a
prediction, we have for the closed case (just remove the term
$d(p_{n},\mathcal{O})$ for the open case):

$|$

Since the hypothetical algorithm moves between predictions and requests, we
get the following bound on $|$

$\begin{gathered}|\alg{}^{\prime}|_{I}\leq
t^{*}+\left(\sum_{i=s}^{n-1}d(p_{\sigma_{1}[i]},x_{\sigma_{1}[i]})+d(x_{\sigma_{1}[i]},p_{\sigma_{1}[i+1]})\right)+d(p_{\sigma_{1}[n]},x_{\sigma_{1}[n]})+d(x_{\sigma_{1}[n]},\mathcal{O})\enspace.\end{gathered}$

Using the triangle inequality $d(x_{\sigma_{1}[i]},p_{\sigma_{1}[i+1]})\leq
d(x_{\sigma_{1}[i]},p_{\sigma_{1}[i]})+d(p_{\sigma_{1}[i]},p_{\sigma_{1}[i+1]})$,
we get

$\displaystyle|$ $\displaystyle\leq
t^{*}+\left(\sum_{i=s}^{n-1}d(p_{\sigma_{1}[i]},p_{\sigma_{1}[i+1]})+2d(x_{\sigma_{1}[i]},p_{\sigma_{1}[i]})\right)+2d(p_{\sigma_{1}[n]},x_{\sigma_{1}[n]})+d(p_{\sigma_{1}[n]},\mathcal{O})$
$\displaystyle\leq|$

Now, we shift our attention to the values $|\operatorname{OPT}_{I}|_{I}$ and
$|\operatorname{OPT}_{I_{H}}|_{I_{H}}$. Our goal will be to show that
$|\operatorname{OPT}_{I}|_{I}\geq|\operatorname{OPT}_{I_{H}}|_{I_{H}}-2\Delta$.
Since
$|\operatorname{OPT}_{I_{H}}|_{I_{H}}\leq|\operatorname{OPT}_{I}|_{I_{H}}$, it
suffices to show
$|\operatorname{OPT}_{I}|_{I}\geq|\operatorname{OPT}_{I}|_{I_{H}}-2\Delta$. We
can assume that $\operatorname{OPT}$ moves to the requests eagerly, following
an order $\sigma$, and leaves as soon as they are released. Similarly to
before, let $t^{*}$ be the last time that the tour of $\operatorname{OPT}_{I}$
in the instance $I_{H}$ induces some waiting, and let $q_{\sigma[s]}$ be that
request (or the origin for $s=0$, which also implies $t^{*}=0$). It follows
then that

$|\operatorname{OPT}_{I}|_{I_{H}}=t^{*}+\sum_{i=s}^{n-1}d(p_{\sigma[i]},p_{\sigma[i+1]})+d(p_{\sigma[n]},\mathcal{O})\enspace.$

But, because the request $q_{\sigma[s]}$ is unreleased before $t^{*}$ (the
case $s=0$ implies $t^{*}=0$, so the conclusion will still hold), we also have

$\displaystyle|\operatorname{OPT}_{I}|_{I}$ $\displaystyle\geq
t^{*}+\sum_{i=s}^{n-1}d(x_{\sigma[i]},x_{\sigma[i+1]})+d(x_{\sigma[n]},\mathcal{O})$
$\displaystyle\geq
t^{*}+\left(\sum_{i=s}^{n-1}-d(x_{\sigma[i]},p_{\sigma[i]})+d(p_{\sigma[i]},p_{\sigma[i+1]})-d(p_{\sigma[i+1]},x_{\sigma[i+1]})\right)$
$\displaystyle\hskip
22.0pt-d(x_{\sigma[n]},p_{\sigma[n]})+d(p_{\sigma[n]},\mathcal{O})$
$\displaystyle\geq|\operatorname{OPT}_{I}|_{I_{H}}-2\Delta\enspace,$

where we use the triangle inequality for the second inequality. The smoothness
of the general algorithm follows. We have $|$, which implies $|$. This gives
us $\frac{|\alg|_{I}}{|\operatorname{OPT}_{I}|_{I}}\leq 3/2+5\eta.$

LA-SWAG achieves smoothness that is linear in the error (besides the optimal
consistency bound of 3/2). We now show that this linear dependency is
necessary for the open case.

######  Proposition 4.3 (Smoothness Lower Bound).

No algorithm can have a better competitive ratio than
$\left(3/2+\eta/2\right)$ for the open variant on an instance with prediction
error $\eta\in[0,1/3]$.

######  Proof 4.4.

Let $\eta\in[0,1/3]$, and define $\epsilon$ such that
$\eta=\epsilon/(2-\epsilon)$ (i.e., $\epsilon=2\eta/(1+\eta)$). Note that
$\epsilon\in[0,1/2]$. Consider the graph represented in Figure 1.

$1$$1$$\epsilon$$1-2\epsilon$$\epsilon$$\epsilon$$1-2\epsilon$$\epsilon$$\mathcal{O}$$A$$B$$C$$D$$E$$F$
Figure 1: An example for the open variant showing a metric space in which the
competitive ratio has to scale linearly with $\eta$ for values of the latter
up to $1/3$.

There are two requests, $q_{1}$ predicted to be in location $p_{1}=A$ and
$q_{2}$ predicted to be in $p_{2}=B$. We assume w.l.o.g. that at time $t=1$
the algorithm is on $[O,B]$. Then $q_{1}$ is released at $t=1$ on its
predicted location ($x_{1}=p_{1}=A$). Note that at time $2-\epsilon$, the
algorithm must be at distance at least $\epsilon$ from $A$ (in particular, it
cannot be on $(C,A]$ or on $(E,A]$). If it is on $[B,E]$, then we release the
second request $q_{2}$ on $D$. Otherwise, we release it on $F$. Suppose
w.l.o.g. that the first case occurs. Then the algorithm needs at least one
unit of time to serve both requests (at $t=2-\epsilon$ it is not on $(B,C)$
and at distance at least $\epsilon$ from $A$). So $|$.

The optimal solution is to serve $q_{1}$ at $t=1$ and $q_{2}$ at
$t=2-\epsilon.$ Note that $\eta=\frac{\epsilon}{2-\epsilon}$ is indeed the
error in the prediction. Then

$|$

###  4.2 Robustness

We now deal with the robustness analysis. We first upper bound the robustness
of LA-SWAG, and then complement this analysis with some lower bounds.

######  Remark 4.5 (3-Robustness).

It is easy to see that LA-SWAG is 3-robust (in both the closed and open
variants). Indeed, let $t_{f}$ be the time when the final request is released.
Of course $|\operatorname{OPT}|\geq t_{f}$. Then, at $t_{f}$ the server can be
at most $|\operatorname{OPT}|$ away from the origin. Since, thanks to the
breaking rule, the algorithm serves the remaining requests optimally after
$t=t_{f}$, to return back to the origin and then follow $\operatorname{OPT}$
is an upper bound of its cost. So, $|$ and the robustness of the algorithm
with predictions is at most $3$.

We now improve this bound, both for the closed and open cases, both in general
metrics and for specific metric spaces.

Let us first deal with the closed variant.

#### Closed variant.

######  Lemma 4.6.

LA-SWAG is $2.75$-robust for closed OLTSP in general metric spaces.

######  Proof 4.7.

Let $T\geq 0$ be the time computed in Step 2 of LA-SWAG. It depends both on
the predicted locations of the requests and the (real) release times. Let
$c\in(0,1]$ be a real constant to be determined later. We denote by $\rho$ the
ratio $|$.

  * •

If $T>|\operatorname{OPT}|$, then  starts following an optimal tour from the
origin at time $t=t_{f}\leq|\operatorname{OPT}|$ because of the breaking rule.
So, $|$ and

$\leq/2\enspace.$ (6)

  * •

If $0\leq T\leq c\cdot|\operatorname{OPT}|$, then there is an order of
requests $\sigma_{0}$ that the general algorithm keeps track of such that
$T\geq\ell^{\prime}_{\sigma_{0}}/2$, $\alpha^{\prime}_{\sigma_{0}}(T)\geq 1/2$
and $\beta^{\prime}_{\sigma_{0}}(T)=1/2$, where the parameters with the prime
symbol $\ell^{\prime},\alpha^{\prime},\beta^{\prime}$ are computed on the
predicted locations and the real release times.

Let $\sigma_{1}$ be the tour that our algorithm will follow at $T$. Thus, we
have that

$\big{(}1-\beta^{\prime}_{\sigma_{1}}(T)\big{)}\ell^{\prime}_{\sigma_{1}}\leq\big{(}1-\beta^{\prime}_{\sigma_{1}}(T)\big{)}\ell^{\prime}_{\sigma_{1}}=\ell^{\prime}_{\sigma_{1}}/2\leq
T\enspace.$

Since $\beta^{\prime}\leq 1/2$, it holds that
${1-\beta^{\prime}_{\sigma_{1}}(T)}\geq 1/2$ and
$\ell^{\prime}_{\sigma_{1}}\leq 2T$. Hence, with the assumption $T\leq
c\cdot|\operatorname{OPT}|$ we get that

$\ell^{\prime}_{\sigma_{1}}\leq 2c\cdot|\operatorname{OPT}|\enspace.$ (7)

After $T$, the algorithm follows the order of requests $\sigma_{1}$. It first
goes to the predicted location of a request and waits for its release. Then,
it goes to the real location of the request and serves it. When all requests
are released, the algorithm computes and follows an optimal path that serves
the remaining requests and returns to the origin.

The furthest distance from the origin that a predicted request can have is
$L_{P}\leq\ell^{\prime}_{\sigma_{1}}/2$. From (7), we get $L_{P}\leq
c\cdot|\operatorname{OPT}|$. On the other hand, the furthest distance from the
origin that a real request can have is
$L_{R}\leq\ell_{\operatorname{OPT}}/2\leq|\operatorname{OPT}|/2$, where
$\ell_{\operatorname{OPT}}$ is the length of the optimal tour.

$p_{j}$$\mathcal{O}$$x_{i}$$z$ Figure 2: The case for general metrics when the
server goes from the furthest predicted location $p_{j}$ to the location
$x_{i}$ of the furthest (real) request $q_{i}$ or vice-versa. The algorithm
($z$) is always on the shortest path between $x_{i}$ and $p_{j}$.

Now let us consider the furthest distance that  can have from the origin at
time $t=t_{f}$.  during its tour moves between predicted and real locations of
requests until time $t_{f}$. In the following, we denote the position of  at
$t_{f}$ by $z$. The worst-case occurs if  goes from the furthest predicted
request to the furthest real request or vice-versa (see Fig. 2). From the
triangle inequality, we have that $d(z,\mathcal{O})\leq
d(\mathcal{O},x_{i})+d(x_{i},z)$ and $d(z,\mathcal{O})\leq
d(\mathcal{O},p_{j})+d(p_{j},z)$. Hence, we have $2d(z,\mathcal{O})\leq
d(\mathcal{O},x_{i})+d(\mathcal{O},p_{j})+d(x_{i},z)+d(p_{j},z)$. Since the
algorithm is on the shortest path between $x_{i}$ and $p_{j}$, we get
$d(x_{i},p_{j})=d(x_{i},z)+d(p_{j},z)$. Using the triangle inequality again it
follows that $d(x_{i},p_{j})=d(x_{i},z)+d(p_{j},z)\leq
d(\mathcal{O},x_{i})+d(\mathcal{O},p_{j})$. Therefore,

$2d(z,\mathcal{O})\leq
d(\mathcal{O},x_{i})+d(\mathcal{O},p_{j})+d(x_{i},z)+d(p_{j},z)\leq
2(d(\mathcal{O},x_{i})+d(\mathcal{O},p_{j}))\enspace,$

which implies

$d(z,\mathcal{O})\leq d(\mathcal{O},x_{i})+d(\mathcal{O},p_{j})\leq
L_{R}+L_{P}\leq(1/2+c)\cdot|\operatorname{OPT}|\enspace.$ (8)

The strategy that returns to the origin at time $t=t_{f}$ and then follows
$\operatorname{OPT}$ is clearly an upper bound of $|$, and thus from (8) and
the fact that $t_{f}\leq|\operatorname{OPT}|$ it follows that $|$ and

$\rho\leq 2.5+c\enspace.$ (9)

  * •

Else, $c\cdot|\operatorname{OPT}|<T\leq|\operatorname{OPT}|.$ Then,  is at
most $(|\operatorname{OPT}|-T)$ away from the origin at
$t=|\operatorname{OPT}|$. So, the following strategy is clearly an upper bound
of $|$: an algorithm that is in the origin at
$t=|\operatorname{OPT}|+|\operatorname{OPT}|-T$ and then follows
$\operatorname{OPT}$ to serve all requests. Thus, we get

$\leq/\frac{|\operatorname{OPT}|+|\operatorname{OPT}|-T+|\operatorname{OPT}|}{|\operatorname{OPT}|}<\frac{(3-c)|\operatorname{OPT}|}{|\operatorname{OPT}|}=3-c\enspace.$
(10)

We can see that the case leading to (6) will not be a factor in the
determination of the robustness, so we can ignore it. We optimize (9) and (10)
simultaneously. It is easy to see that the best value is attained for
$c=0.25$, giving a robustness of $2.75$.

Moreover, we observe that we can get a better robustness guarantee with almost
the same proof for the special metric spaces of Euclidean spaces and trees.
More specifically, we get the following lemma.

######  Lemma 4.8.

LA-SWAG is $2.5$-robust for closed OLTSP in Euclidean spaces and in trees.

######  Proof 4.9.

The proof is almost the same as the proof of Lemma 4.6. The only difference is
that since it holds that
$d(z,\mathcal{O})\leq\max\\{d(\mathcal{O},x_{i}),d(\mathcal{O},p_{j})\\}\leq\max\\{c\cdot|\operatorname{OPT}|,1/2\cdot|\operatorname{OPT}|\\}$
in these metric spaces (as the algorithm is on a shortest path between $x_{i}$
and $p_{j}$), we can actually get a better upper bound than that of inequality
(9), namely

$\rho\leq\frac{t_{f}+\max\\{d(\mathcal{O},x_{i}),d(\mathcal{O},p_{j})\\}+|\operatorname{OPT}|}{|\operatorname{OPT}|}\leq
2+\max\\{1/2,c\\}\enspace.$ (11)

We can again ignore (6). Considering (10) and (11), we get robustness $2.5$
with $c=0.5$.

From Lemma 4.6 and 4.8 we directly get the following theorem for the
robustness of LA-SWAG in the closed variant.

See 1.2

######  Remark 4.10 (Tightness of Analysis for Closed Variant
2.5-Robustness.).

The 2.5-robustness bound of LA-SWAG given in Lemma 4.8 is tight even on the
line, as shown in the following example. There are two requests. The real
request locations are $x_{1}=1,x_{2}=0$, released at times 1 and 2,
respectively, and the predictions are $p_{1}=0,p_{2}=-1$. Note that at time 1
our algorithm will start moving towards the prediction $p_{2}$, because half
the tour $\mathcal{O}\rightarrow p_{2}\rightarrow p_{1}\rightarrow\mathcal{O}$
is “released” and enough time (half of its length) has passed.222In fact, this
is the only permutation that LA-SWAG will be provided with by the oracles we
define later. To ensure this, we can perturb $p_{1}$ to the left of the origin
by some arbitrarily small $\epsilon$ and then let $\epsilon\to 0$. Hence, it
will definitely choose to follow this permutation. It will keep moving and
reach position $-1$ at time $2$, since $p_{2}$’s corresponding request is
unreleased until that time. Then, after reaching this unfavorable position,
can only go back to the origin and copy $\operatorname{OPT}$. We see that $|$
while $\operatorname{OPT}=2$, so the algorithm has competitive ratio $2.5$.

#### Open variant.

In fact, we can also show a better than 3 robustness bound even for the open
variant, where only the triangle inequality is assumed. The trick is to
consider another option for finishing up, namely to go to the last request
served by $\operatorname{OPT}$, say $q_{\ell}$, and then copy
$\operatorname{OPT}$ backwards. It is clear that this copy also takes at most
$|\operatorname{OPT}|$ time, since there might not be a request at the origin.
Hence, it remains to show that we can reach $q_{\ell}$ or the origin
relatively fast.

######  Lemma 4.11.

LA-SWAG is $\left(3-\frac{1}{6}\right)$-robust for open OLTSP in general
metric spaces.

######  Proof 4.12.

Note that LA-SWAG, at the final release time $t_{f}$, is on some shortest path
from a prediction to the location of a request or vice versa (or from the
origin to a prediction, which is trivial or can be thought of as a request
location). Now, let $p$ be that prediction and $q$ the request with actual
location $x$. We do not distinguish whether the movement is made from $p$ to
$x$ or vice versa. Consider the path $P_{1}$, which moves from $z$ (the
position of the server at time $t_{f}$) to $p$ and then to $\mathcal{O}$, and
the path $P_{2}$ which moves from $z$ to $x$ and then to $x_{\ell}$, the
location of the last request served by $\operatorname{OPT}$. Now, let
$d_{p}=d(z,p)$ and $d_{x}=d(z,x)$. Since is on the shortest path from $p$ to
$x$ or vice versa, it holds that $d_{p}+d_{x}=d(p,x)$. Note that we have

$\displaystyle min\\{|P_{1}|,|P_{2}|\\}$
$\displaystyle\leq\frac{|P_{1}|+|P_{2}|}{2}=\frac{d_{p}+d_{x}+d(p,\mathcal{O})+d(x,x_{\ell})}{2}$
$\displaystyle\leq
d(p,\mathcal{O})+\frac{d(x,x_{\ell})+d(x,\mathcal{O})}{2}\leq\frac{|\operatorname{OPT}|}{2}+d(p,\mathcal{O})\enspace.$

This means that we can finish in at most $(2.5+\gamma)|\operatorname{OPT}|$
overall, where $\gamma=\frac{d(p,\mathcal{O})}{|\operatorname{OPT}|}$. Now, we
can apply the same idea from the proofs for the closed case. That is, let
$T=c\cdot|\operatorname{OPT}|$, where $T$ is the start time of the algorithm.
We see that $d(p,\mathcal{O})\leq 2c\cdot|\operatorname{OPT}|$, otherwise the
conditions necessary for the algorithm to start would not be satisfied at $T$.
Also, a trivial bound for the performance is $(3-c)|\operatorname{OPT}|$.
Hence, on the one hand we have $\frac{|\alg|}{|\operatorname{OPT}|}\leq
2.5+2c$ and on the other $\frac{|\alg|}{|\operatorname{OPT}|}\leq 3-c$, and
these bounds hold simultaneously. Thus, overall we have that
$\frac{|\alg|}{|\operatorname{OPT}|}\leq 3-\frac{1}{6}$ by setting
$c=\frac{1}{6}$.

Also, we can improve the bound when dealing with trees.

######  Lemma 4.13.

LA-SWAG is $\left(3-1/3\right)$-robust for open OLTSP in trees.

######  Proof 4.14.

Consider a prediction $p$ and the location $x$ of a request $q$. For
simplicity, let us assume that $p$ and $x$ are vertices in the tree, otherwise
we could simply add vertices at these locations. Note that in this case, when
moving from $p$ to $x$ or vice versa, first moves to the lowest common
ancestor of $p$ and $x$ and then continues along the path to its destination.
This means that at any point through this movement, it is on one of $x$ or
$p$’s paths to the origin. In particular, this is also true at $t=t_{f}$. If
it is on the path to $p$, then the distance to the origin is at most $p$’s
distance to the origin. If it is on the path to $x$, then it means that it is
also on some point along the path that $\operatorname{OPT}$ would take. Thus,
it can complete the objective by first moving to either endpoint of the path
and then copying it, which takes at most $(1+2c)|\operatorname{OPT}|$ or
$3/2|\operatorname{OPT}|$ time in total, depending on the previous case
distinction, where $c$ is the fraction of $|\operatorname{OPT}|$ waited.
Hence, we have the bounds $2.5,2+2c,3-c$, and so we get the desired
competitive ratio by considering $c=1/3$.

The two previous lemmata give us our main robustness theorem for the open
variant.

See 1.3

######  Remark 4.15 (Tightness of Analysis for Open Variant
$\left(3-\frac{1}{3}\right)$-Robustness.).

The $\left(3-\frac{1}{3}\right)$-robustness bound of LA-SWAG given in Lemma
4.13 is tight, even on a line. To see this, we place (on the real line) a
prediction at $-1$ and the real request at $1.5$, released at $t=1.5$. Note
that at time $t=0.5$, our algorithm embarks on its path to the prediction. It
reaches $-1$ at $t=1.5$. This means that it cannot finish before $t=4$, since
it has to travel from $-1$ to $1.5$, starting at $t=1.5$. However, the optimal
time is $1.5$, yielding a competitive ratio of $8/3=3-1/3$.

#### Consistency-Robustness tradeoff lower bound for the open variant.

We conclude this section by showing a consistency-robustness tradeoff lower
bound for the open variant.

######  Proposition 4.16.

Let be an algorithm for the open variant with consistency guarantee
$2-\lambda$, where $\lambda\in[0,1]$. Then, cannot be
$\left(2+\lambda-\epsilon\right)$-robust, for any $\epsilon>0$.

######  Proof 4.17.

We show this on the line. We place a prediction at $-1$ and the real request
at $1$, which will be released at $t=1$. Since is
$\left(2-\lambda\right)$-consistent, it must be located at a position not
strictly to the right of $-\lambda$ at $t=1$, otherwise it could not reach the
prediction by time $2-\lambda$, which would be a contradiction to ’s
consistency if the prediction was correct and released at $t=1$. Therefore,
can only reach the real request at or later than $t=2+\lambda$, which
concludes the proof since $|\operatorname{OPT}|=1$.

Note that the above implies that the best possible robustness for any
$1.5$-consistent algorithm is $2.5$, placing our algorithm relatively close to
the underlying Pareto front.

##  5 A single-exponential time algorithm for general metrics

In the case of perfect predictions, using SWAG and Lemma 3.3 we can reduce the
factorial running time of the algorithm in [13] for general metrics. We will
show that an exponential number of permutations suffices to have a domination
oracle. After that, using the scheme of LA-SWAG and the theorems proved in the
previous section we will get an exponential-time algorithm that is
$3/2$-consistent, smooth and robust.

At each time $t$ there is a set $R(t)$ of released requests and a set $U(t)$
of unreleased requests. For ease of explanation we refer to the closed case
here, but the open case is similar. Consider an arbitrary permutation $\sigma$
of the $n$ requests at time $t$. A corresponding dominating tour for this
permutation can be constructed as follows. First, find the first unreleased
request $u\in U(t)$ in the permutation $\sigma$. The released requests before
$u$ in the permutation form a subset $R^{\prime}(t)\subseteq R(t)$ of released
requests. Then, a corresponding general dominating tour would be the optimal
TSP path that starts from the origin, serves all requests in $R^{\prime}(t)$
and ends at request $u$ plus the optimal TSP path that starts from $u$, serves
all requests in $\big{(}R(t)\setminus
R^{\prime}(t)\big{)}\cup\big{(}U(t)\setminus\\{u\\}\big{)}$ and returns to the
origin. We will call these tours (corresponding) _general dominating tours_.

Throughout this section, we will assume for ease of exposition that $t_{1}\leq
t_{2}\leq\dots\leq t_{n}$ and use $t_{0}=0$ and $t_{n+1}=\infty$. At time
$t_{i}$, with $i\leq n$, we compute the set of general dominating tours
$D_{i}$ given the sets $R(t_{i})$ and $U(t_{i})$. Together with the previously
computed sets, it is then provided to SWAG as set
$S(t_{i})=\bigcup_{j=0}^{i}D_{j}$.

######  Definition 5.1 (General Dominating Permutations).

Let $\sigma$ be a permutation of the $n$ requests. Given a time $t$, there is
a set $R(t)$ of released requests and a set $U(t)$ (assume for now that
$U(t)\neq\emptyset$) of unreleased requests. Let $u\in U(t)$ be the first
unreleased request in the permutation $\sigma$ and $R^{\prime}(t)\subseteq
R(t)$ be the set of released requests that precedes $u$ in the permutation. A
corresponding general dominating tour of $\sigma$ at time $t$ consists of:

  1. 1.

an optimal TSP path $TSP_{\mathcal{O}-R^{\prime}-u}$ that starts from the
origin, serves all requests in $R^{\prime}(t)$ and ends at request $u$,

  2. 2.

and an optimal TSP path $TSP_{u-B-\mathcal{O}}$ that starts from request $u$,
serves all requests in $B=\big{(}R(t)\setminus
R^{\prime}(t)\big{)}\cup\big{(}U(t)\setminus\\{u\\}\big{)}$ and returns to the
origin.

Note that an optimal TSP path here is computed ignoring the release times of
the requests. The length $\ell$ of the corresponding general dominating tour
is then

$\ell=\ell_{TSP_{\mathcal{O}-R^{\prime}-u}}+\ell_{TSP_{u-B-\mathcal{O}}}\enspace.$

If $U(t)=\emptyset$, then $|R(t)|=n$, every request is released and we define
the corresponding general dominating tour for every $\sigma$ to be an optimal
TSP tour that starts from the origin, serves all requests and returns again to
the origin (the same optimal TSP tour for every $\sigma$).

The definition of the corresponding general dominating path of a permutation
$\sigma$ for the open case is similar, i.e., instead of ending at the origin,
a path ends at an arbitrary request from $\big{(}R\setminus
R^{\prime}\big{)}\cup\big{(}U\setminus\\{u\\}\big{)}$, and thus we omit it.
From now on we will refer to general dominating permutations (paths or tours).

######  Proposition 5.2.

Let $\sigma$ be a permutation of the $n$ requests. Then, at each time $t$,
there exists a corresponding general dominating permutation $\sigma^{\prime}$
of $\sigma$. Equivalently, it holds that

$\ell_{\sigma^{\prime}}\leq\ell_{\sigma}$ (12)

and

$(1-\alpha_{\sigma^{\prime}}(t))\ell_{\sigma^{\prime}}\leq(1-\alpha_{\sigma}(t))\ell_{\sigma}\enspace.$
(13)

######  Proof 5.3.

Since time $t$ is fixed here, the time dependence will be suppressed for
convenience. At time $t$, there is a set of released requests $R$ and a set of
unreleased requests $U$ (suppose for now that $U\neq\emptyset$). Let $u\in U$
be the first unreleased request in the permutation $\sigma$ at time $t$ and
$R^{\prime}\subseteq R$ be the set of released requests that precedes $u$ in
the permutation. So, we know that permutation $\sigma$ serves first the set
$R^{\prime}$ of requests, then the request $u$ and after that, the rest of the
requests (set $B=\big{(}R\setminus
R^{\prime}\big{)}\cup\big{(}U\setminus\\{u\\}\big{)}$). So, we can write its
length $\ell_{\sigma}$ as

$\ell_{\sigma}=\ell_{\mathcal{O}-R^{\prime}-u}+\ell_{u-B-\mathcal{O}}\enspace.$

It is easy to see that the value $(1-\alpha_{\sigma})\ell_{\sigma}$ is exactly
the length of the part of the tour starting with the unreleased request $u$,
i.e., $\ell_{u-B-\mathcal{O}}$. Similarly for its corresponding general
dominating permutation $\sigma^{\prime}$, we have that
$(1-\alpha_{\sigma^{\prime}})\ell_{\sigma^{\prime}}=\ell_{TSP_{u-B-\mathcal{O}}}$.
It is also clear that
$\ell_{TSP_{\mathcal{O}-R^{\prime}-u}}\leq\ell_{TSP_{\mathcal{O}-R^{\prime}-u}}$
and $\ell_{TSP_{u-B-\mathcal{O}}}\leq\ell_{TSP_{u-B-\mathcal{O}}}$. Thus, we
get (12) and (13).

If $U=\emptyset$, then $\sigma^{\prime}$ is an optimal TSP tour that serves
all requests and returns to the origin and
$\alpha_{\sigma}=\alpha_{\sigma^{\prime}}=1$. Therefore, we have again that
(12) and (13) hold.

Consequently, at each time $t$, a general dominating permutation
$\sigma^{\prime}$ dominates permutation $\sigma$.

Next, we give the formal definition of a general dominating set $D_{i}$.

######  Definition 5.4 (General dominating set).

We define the general dominating set $D_{i}$, with $i\in\\{0,1,2,\dots,n\\}$,
as the set which contains all general dominating permutations that are
generated with sets $R(t_{i})$, $U(t_{i})$ and every possible selection of
$R^{\prime}(t_{i})\subseteq R(t_{i})$ and $u\in U(t_{i})$.

For the set $S$ of permutations SWAG uses each time, it holds that
$S(t)\subseteq S(t^{\prime})$ for every $t\leq t^{\prime}$, since we provide
the algorithm at time $t_{i}$ with the union of all $D_{k},k\leq i\leq n$.
Moreover, the general dominating set $D_{i}$ dominates all permutations for
all $t<t_{i+1}$. Thus, we will show that an oracle $\mathcal{D}$ which outputs
at any time $t\in[t_{i},t_{i+1})$ the general dominating sets
$\bigcup_{j=0}^{i}D_{j}$ for each $i\in\\{0,1,2,\dots,n\\}$, is a domination
oracle. Before doing that, let us compute the running time of such an
algorithm. First, we show that the number of general dominating permutations
which are contained in the set $\bigcup_{j=0}^{i}D_{j}$ with $i\leq n$, can
always be upper bounded by $2^{n}$.

######  Lemma 5.5.

There always exists a set $\bigcup_{j=0}^{i}D_{j}$ which consists of at most
$2^{n}$ distinct general dominating permutations, for all
$i\in\\{0,1,\dots,n\\}$.

######  Proof 5.6.

Consider a general dominating permutation as it is defined in Definition 5.1.
We only consider the closed variant here, the proof is analogous for the open
variant. Suppose that we always take the permutation corresponding to the tour
which consists of the (unique) lexicographically first optimal TSP paths
$TSP_{\mathcal{O}-R^{\prime}-u}$ and $TSP_{u-B-\mathcal{O}}$. Any such
permutation is completely determined by the set
$Q^{\prime}=R^{\prime}(t_{i})\cup\\{u\\}$ for any value of $i$, as $u$ is the
only unreleased request in $Q^{\prime}$. Also, all sets $Q^{\prime}$ are
subsets of the set of all $n$ requests, and thus there can be at most $2^{n}$
distinct ones. Note that if $u$ does not exist, i.e., all requests have been
released, there exists only a single lexicographically first optimal TSP tour.
Consequently, we can always construct the set $\bigcup_{j=0}^{i}D_{j}$
consisting of at most $2^{n}$ distinct (general dominating) permutations for
all $i\in\\{0,1,\dots,n\\}$.

Next, we use Lemma 5.5 to show the following theorem for the running time of
LA-SWAG.

######  Lemma 5.7.

LA-SWAG that uses the general dominating sets runs in $O(n^{2}\cdot 2^{n})$
time complexity for both closed and open variants of OLTSP.

######  Proof 5.8.

From Lemma 5.5, there are at most $N=2^{n}$ permutations in the set $S$ the
algorithm uses. At $t=0$, we can precompute a set $D$ of general dominating
permutations of size at most $2^{n}$ by Lemma 5.5 in time $O(n^{2}2^{n})$
using dynamic programming [15, 24]. Then, every time $t_{j}$ a request is
released, we can select the right set $D_{j}\subseteq D$ of general dominating
permutations (from all the possible general dominating permutations we have
precomputed), add it to the previous ones and provide them to the algorithm
acting as the oracle. From Corollary 4.1, we get that LA-SWAG with the general
dominating sets runs in $O(n^{2}\cdot 2^{n})$ time.

Now we are ready to state and prove the main theorem of this section.

See 1.4

######  Proof 5.9.

If the two conditions of the domination oracle are satisfied for the general
dominating sets, then we can use LA-SWAG and Lemma 3.3 to get an exponential
time algorithm for open and closed LA-OLTSP that is $3/2$-consistent. It is
obvious that Condition $1$ is satisfied as $S(t)\subseteq S(t^{\prime})$ for
every $t\leq t^{\prime}$. Condition $2$ is also satisfied since for each time
$t$ we have a corresponding dominating permutation for every possible subset
of $R(t)$ and choice of $u$, and thus for every permutation $\sigma$.
Therefore, we apply Lemma 3.3 and get a consistency of $3/2$. For smoothness
and robustness, we use Theorems 1.1, 1.2 and 1.3 directly, completing the
proof.

##  6 Polynomial/FPT time algorithms for specific metric spaces

In this section, we show how to build polynomial/FPT time algorithms based on
the general framework for specific metric spaces, namely trees, rings and
flowers. Specifically, we show how to build (in polynomial/FPT time) a
dominating set of polynomial/FPT size in each of these cases. These will
dominate a so-called sensible set of permutations in each case, which we
define later. We focus now on the closed variant and explain later how to deal
with the open case. Also, for the sake of simplicity, we will define the “new”
dominating permutations that will be added to the oracle’s set whenever a
request is released. It is to be understood that the oracle maintains the
union of all permutations generated and provides that to LA-SWAG.

We also need to implement the “cleanup” step of LA-SWAG, where a computation
of an optimal classical (offline, without release times) TSP path/tour is
required. We describe briefly how this is done in Subsection 6.5. Note,
however, that these runtimes are small enough (in fact, in $O(n)$) so that the
bottleneck will be the cardinality of the set of dominating permutations for
the runtime of LA-SWAG.

Now, let us start working towards the definitions and constructions promised.

######  Definition 6.1 (Safe Set).

Let $X$ be a set of request locations. A set of permutations $\Pi$ is safe for
$X$ if for any assignment $f$ of release times to each location in $X$, there
exists a permutation $\pi\in\Pi$ which is optimal for the resulting input
$Q=\\{(x,f(x))\>|\>x\in X\\}$.

Note that the set of all permutations is safe. However, as we will see, we can
define sets of permutations that follow some desirable structure but are still
safe. We will call such sets sensible. It is these sets which we will dominate
instead of the set of all permutations. Recall that LA-SWAG provides all the
guarantees it does if the oracle that it uses dominates a safe set, which
motivates this entire section.

In general, we will show domination by the following steps. First, we will
argue that the dominating permutation serves a superset of the requests served
by the dominated permutation in no more time before reaching the first
unreleased request $q$ (in the dominated permutation). Afterwards, an optimal
solution that serves the rest of the requests will be followed. The above
imply domination.

###  6.1 Trees

In this section, we consider metric spaces that are shaped like a tree. That
is, we have continuous spaces that can be embedded into trees with lengths on
the edges, where these are positive (and correspond to the traversal time of
the edge) and the edges incident to a leaf can have “infinite” length. The
request may appear on nodes of the tree or at some point along the edges. For
example, a request may appear 1 unit away from $q$ and 2 units away from $p$,
where $p$ and $q$ are nodes of the tree connected by an edge with length 3.
This corresponds to requests along some street between crossings in a real-
world scenario. It is important that we allow the leaf edges to have infinite
length in order to be able to subsume the line and star metrics.

#### Sensible set.

For such a metric space, we can focus on a very specific set of sensible
permutations. Let us describe the idea behind the definition of these first.
Suppose that an algorithm serves a request $q$ at time $t$. When the algorithm
finishes, say at time $t_{f}$, it will be located at the origin $\mathcal{O}$.
There is only one path $\mathcal{P}_{q}$ from $q$ to $\mathcal{O}$, and it
must be traversed after $t$. Hence, any request $q^{\prime}$ on
$\mathcal{P}_{q}$ will be visited at some point after $t$ anyway. Therefore,
there is no reason for the algorithm to try and serve $q^{\prime}$ before time
$t$ (i.e., before serving $q$), since it would serve $q^{\prime}$ on the way
back to the origin after $t$ anyway. From this, it follows that for any
sequence of requests $S_{q}$ encountered along a path $\mathcal{P}_{q}$
towards the origin may be safely assumed to be a subsequence of the optimal
permutation. This motivates the following.

######  Definition 6.2 (Sensible Set for Trees).

Let $\mathcal{T}$ be a tree rooted at the origin $\mathcal{O}$ and $X$ a set
of request locations on $\mathcal{T}$. The set $\Pi_{s}(\mathcal{T},X)$ of
sensible permutations consists of all permutations $\pi$ where the following
holds. Let $\pi=x_{\pi(1)},x_{\pi(2)},\dots,x_{\pi(n)}$. For any $x_{\pi(i)}$
and any $x_{\pi(j)}$ on the path $\mathcal{P}_{x_{\pi(i)}}$ from $x_{\pi(i)}$
to the origin, we have $j>i$.

######  Claim 1.

For any tree $\mathcal{T}$ and any set of request locations $X$, the set
$\Pi_{s}(\mathcal{T},X)$ is safe.

######  Proof 6.3.

Let $\pi$ be an arbitrary permutation and $f$ an arbitrary assignment of
release times to $X$. We will show that there exists
$\pi_{s}\in\Pi_{s}(\mathcal{T},X)$ with $|\pi_{s}|\leq|\pi|$, where $|\pi|$
denotes the completion time of the tour associated to permutation $\pi$ under
$f$. Let $z(t)$ denote the position of a server following $\pi$ at time $t$.
Let $l_{i}=\max\\{t\>|\>z(t)=x_{i}\\}$. Now, we sort the $l_{i}$ values and
extract the sorted indices to get
$\pi_{s}=x_{\pi_{s}(1)},x_{\pi_{s}(2)},\dots,x_{\pi_{s}(n)}$. In other words,
$\pi_{s}$ is derived by the ordering of the requests based on their last visit
by a server following $\pi$. By construction,
$\pi_{s}\in\Pi_{s}(\mathcal{T},X)$. Now, let us see why $|\pi_{s}|\leq|\pi|$.
Let $t^{run}$ be the final time that $\pi_{s}$ waits on a request location
$x_{\pi_{s}(f)}$. It is easy to see that the release time of $x_{\pi_{s}(f)}$
is at least $t^{run}$. This means that $\pi$ still has to perform a superpath
of $\mathcal{P}_{run}=x_{\pi_{s}(f)}\rightarrow
x_{\pi_{s}(f+1)}\dots\rightarrow x_{\pi_{s}(n)}\rightarrow\mathcal{O}$, after
time $t^{run}$. Let $l_{run}$ denote the length of $\mathcal{P}_{run}$. It is
clear that $|\pi|\geq t^{run}+l_{run}=|\pi_{s}|$.

#### Dominating set.

For the above sensible set, we will define a dominating set whose cardinality
is of order $O(2^{l}\cdot n)$, where $l$ is the number of leaves of the
underlying tree. This yields an algorithm for the problem in trees that runs
in FPT time parameterized by the number of leaves. As the reader may have
already guessed, the idea is to look at subsets of leaves and, more
interestingly, at the paths of those leaves to the origin. That is, for each
subset of the paths of the leaves to the origin and each selection of
intermediate request $q$, we will define the permutation which first optimally
visits the selected subset of leaves finishing at $q$ and then “cleans up” the
rest of the requests starting from $q$ and ending at the origin. The intuition
explaining why this is enough is that any sensible permutation can only have
served a request $q^{\prime}$ before $q$ if it already has served the leaves
“below” $q^{\prime}$.

We can now formally define the dominating permutations. To do that, we
consider the restriction of the tree space to the span of the requests. That
is, for every leaf, if there is a request along its incident edge, we replace
it with a new node which is the request furthest along the possibly infinitely
long edge of the leaf and replace the infinite length by that request’s
distance from the original leaf’s parent. Additionally, we “trim” the tree
past requests when there is no other request along the path to a leaf. Now,
every leaf is a request.

######  Definition 6.4 ($(q,L^{\prime})$-Scan).

Let $\mathcal{T}$ be a rooted tree and $L$ its set of leaves. Let $L^{\prime}$
be a subset of $L$ and $q$ be some request on the tree with location $x$ such
that $x$ is on some path to a leaf in $L^{\prime}$ ($x$ could be along an
edge). Now, let $\mathcal{P}$ be the optimal path starting at the root and
finishing at $x$ while also visiting all leaves in $L^{\prime}$ along the way.
We call $\mathcal{P}$ the $(q,L^{\prime})$-scan of $\mathcal{T}$.

######  Definition 6.5 ($(q,L^{\prime})$-Dominator).

Let $R,U$ be the set of released and unreleased requests at time $t$. Let
$L\subseteq R$ be the subset of released leaves and also let $L^{\prime}$ be a
subset of those leaves. Let $q\in U$ be a furthest unreleased request along a
path to some leaf. Let $\mathcal{P}^{\prime}$ be the $(q,L^{\prime})$-scan of
$\mathcal{T}$. Now, let $U^{\prime}$ be the set of unserved requests after
this scan. That is, $U^{\prime}=U\cup R^{\prime}$, where $R^{\prime}$ is the
subset of released requests not served by $\mathcal{P}^{\prime}$. Construct
the tree $\mathcal{T}^{\prime}$ rooted at $q$, trimmed according to
$U^{\prime}$ and preserving the origin. Let $L^{\prime\prime}$ be the leaves
of $\mathcal{T}^{\prime}$. Let $\mathcal{P}^{\prime\prime}$ be the
$(\mathcal{O},L^{\prime\prime})$-scan of $\mathcal{T}^{\prime}$. The implied
permutation $\pi$ of the tour $\mathcal{P}^{\prime}\mathcal{P}^{\prime\prime}$
is the $(q,L^{\prime})$-dominator of $\mathcal{T}$. We will use the notation
$d_{R,U,\mathcal{T}}(q,L^{\prime})$ to refer to it.

######  Definition 6.6 (Dominating Set for Trees).

Let $R,U$ be as in definition 6.5 and $\mathcal{T},L$ as in definition 6.4.
The tree dominating set is:

$Dom^{\curlyvee}(R,U,\mathcal{T},L)=\bigcup_{q\in U^{*},L^{\prime}\subseteq
L}d_{R,U,\mathcal{T}}(q,L^{\prime}),$

where $U^{*}$ is the set of furthest unreleased requests along the paths to
leaves.

We will now show that this set does indeed dominate the sensible permutations
for trees. Recall that a permutation is sensible for the tree if all sequences
of requests along a single path from a leaf to the root (origin) ordered
decreasingly by distance to the origin are found in the same order in the
permutation.

######  Lemma 6.7 (Tree Domination).

Let $\pi$ be a permutation which is sensible for a tree $\mathcal{T}$ (trimmed
according to the input requests). Let $t$ be the current time and $R,U$ the
released and unreleased requests at time $t$. Also, let $L$ be the set of
leaves of $\mathcal{T}$. Then $Dom^{\curlyvee}(R,U,\mathcal{T},L)$ contains a
permutation $\pi_{dom}$ which dominates $\pi$.

######  Proof 6.8.

Let $\pi=q_{\pi(1)},q_{\pi(2)},\dots,q_{\pi(n)}$. Let $q_{\pi(u)}$ be the
first unreleased request in $\pi$. Let
$R_{served}=\\{q_{\pi(1)},q_{\pi(2)},\dots,q_{\pi(u-1)}\\}$ be the requests
served by $\pi$ before $q_{\pi(u)}$. Let $L^{\prime}=L\cap R_{served}$. Then,
the $(q_{\pi(u)},L^{\prime})$-dominator
$\pi_{dom}=d_{R,U,\mathcal{T}}(q_{\pi(u)},L^{\prime})\in
Dom^{\curlyvee}(R,U,\mathcal{T},L)$ dominates $\pi$. Due to the construction
of $\pi_{dom}$, specifically because an optimal path is calculated for the
parts before and after $q_{\pi(u)}$, we need only show that $\pi_{dom}$ serves
a superset of what $\pi$ serves before $q_{\pi(u)}$ in no more time. Note that
because $\pi$ is sensible, $R_{served}$ must be closed under path-extension.
That is, for every $q\in R_{served}$ and every path $\mathcal{P}$ that $q$ is
on, all requests further down the path $\mathcal{P}$ than $q$ must also be in
$R_{served}$. This implies that all requests in $R_{served}$ are along some
path to a leaf in $L^{\prime}$. But, $\pi_{dom}$ traverses all these paths
before reaching $q_{\pi(u)}$, which proves that $\pi_{dom}$ serves a superset
of $R_{served}$ before $q_{\pi(u)}$. It remains to show that it does so at
least as fast as $\pi$ serves $R_{served}$. This follows because $\pi_{dom}$
is chosen to optimally serve $L^{\prime}$ only and end up at $q_{\pi(u)}$,
which $\pi$ also has to do anyway, completing the proof.

Now, using the above lemma, we obtain our main theorem for trees. The
complexity stems from the term related to the cardinality of the dominating
set in Lemma 3.5, since solving classical TSP on trees is later shown to take
$O(n)$ time.

See 1.5

###  6.2 Ring

#### Sensible set.

The ring turns out to be quite similar to the line. In fact, to define the
sensible permutations for it, we simply need to make the following
observation. If a permutation makes more than one “full” loops around the
ring, it can drop all but the last, since any loop will move through every
request. Since it does not make sense to serve anything before doing a full
loop, the loop can be the first movement after leaving $\mathcal{O}$. After
such a loop, if it even exists, we can assume that the permutation moves along
the ring as if it were a line, i.e., it never crosses the antipodal point of
the origin. Hence, we can define the sensible permutations by branching on
whether a loop is performed and then reduce to the tree case.

######  Definition 6.9 (Sensible Set for the Ring).

Let $X$ be a set of request locations on the ring. The sensible set of
permutations $\Pi_{s}^{\circ}(X)$ consists of all permutations $\pi$ resulting
from the concatenation of $\pi_{loop}$ and $\pi_{line}$ where $\pi_{loop}$ is
a subpermutation covering $X^{\prime}\subseteq X$ in a cyclic fashion and
$\pi_{line}\in\Pi_{s}(T,X\setminus X^{\prime})$, where $T$ is the tree
resulting from splitting the ring at the midpoint across from the origin.

######  Claim 2.

There is always an optimal solution which follows a sensible permutation.

######  Proof 6.10.

We can assume that the ring is a circle with a circumference of $1$. Let us
now consider an optimal solution $\operatorname{OPT}$, and denote by
$\sigma^{*}$ the order in which $\operatorname{OPT}$ serves the requests (a
permutation of the requests). We recall that w.l.o.g. $\operatorname{OPT}$
follows the tour/path $\sigma^{*}$, waiting only at requests’ positions: it
goes from $\mathcal{O}$ to (the position of) $\sigma^{*}[1])$ in time
$d(\mathcal{O},\sigma^{*}[1])$, waits at (the position of) $\sigma^{*}[1]$ if
the request is not released, then from $\sigma^{*}[1]$ to $\sigma^{*}[2]$ in
time $d(\sigma^{*}[1],\sigma^{*}[2])$, …We will then prove that for every
optimal solution $\operatorname{OPT}$, there is another optimal solution
$\operatorname{OPT}^{\prime}$ that is a sensible permutation.

Consider the last time $\operatorname{OPT}$ moves from the one semicircle
$\widehat{\mathcal{O}A\mathcal{O}^{\prime}}$ to the other one
$\widehat{\mathcal{O}B\mathcal{O}^{\prime}}$ (or vice versa) through the
antipodal point $\mathcal{O}^{\prime}$ of the origin (Figure 3).

$\mathcal{O}$$A$$\sigma^{*}[i_{l}]$$\mathcal{O}^{\prime}$$\sigma^{*}[i_{l}+1]$$B$
Figure 3: Ring for the proof of Claim 2.

If $\operatorname{OPT}$ doesn’t cross $\mathcal{O}^{\prime}$ in any moment,
then $\operatorname{OPT}^{\prime}$ can just follow $\operatorname{OPT}$ which
has a zig-zag motion and is a sensible permutation. Otherwise, there is a pair
of consecutive requests $\sigma^{*}[i_{l}]$, $\sigma^{*}[i_{l}+1]$ in the
permutation between which the crossing of $\mathcal{O}^{\prime}$ occurs.
Assume w.l.o.g. that
$\sigma^{*}[i_{l}]\in\widehat{\mathcal{O}A\mathcal{O}^{\prime}}$ and
$\sigma^{*}[i_{l}+1]\in\widehat{\mathcal{O}B\mathcal{O}^{\prime}}$. Then,
$\operatorname{OPT}$ has to move from $\sigma^{*}[i_{l}+1]$ to the origin
without crossing $\mathcal{O}^{\prime}$ again. Let $t^{*}$ be the first time
that $\operatorname{OPT}$ reaches the origin after serving the request at
$\sigma^{*}[i_{l}+1]$. Instead of following $\operatorname{OPT}$,
$\operatorname{OPT}^{\prime}$ can wait in the origin for time $t^{*}-1$ and
then make a full circle
$\widehat{\mathcal{O}A\mathcal{O}^{\prime}B\mathcal{O}}$ without stopping
anywhere. In this case, it reaches $\mathcal{O}$ at time $t^{*}$ (the same as
$\operatorname{OPT}$) serving at least the requests $\operatorname{OPT}$ has
served until that time. Next, $\operatorname{OPT}^{\prime}$ just follows
$\operatorname{OPT}$ which has a zig-zag motion since it never crosses
$\mathcal{O}^{\prime}$ again. Therefore, $\operatorname{OPT}^{\prime}$ is a
sensible permutation and
$|\operatorname{OPT}^{\prime}|\leq|\operatorname{OPT}|$.

#### Dominating set.

As we have discussed, a sensible permutation for the ring can have at most one
full loop in the beginning. Note that if this loop is missing, the case
degenerates to the line, for which we have already defined the dominators.
Therefore, it only remains to define the dominators under the assumption that
$\pi$ does indeed have a loop in the beginning, since then we can just take
the union of the two sets to construct the set of all dominators.

A crucial distinction is whether the current request $q$ of $\pi$ is part of
the loop or not. In the first case, $\pi$ has only traveled a portion of the
loop so far and in the second case it has traveled a full loop and then taken
some possibly complex line-like tour. For every choice of $q$, we define two
permutations, one pertaining to the first case and another to the second one.

The first permutation serves all released requests within $\pi$’s traveled
portion of the loop (in the same direction) and then moves to $q$. From there,
it follows an optimal permutation serving the rest of the requests
(disregarding release times), which can easily be computed for the ring. The
second permutation serves all released requests with a full loop (in clockwise
order if $q$ is to the left arc of the ring and vice versa) and then moves to
$q$. It finishes in the same way by computing an optimal path from $q$ to the
origin. We now define this set of dominating permutations more formally.

######  Definition 6.11 (Crescent Permutations).

Let $R$ be a set of released requests and $U$ be the corresponding set of
unreleased requests on the ring at time $t$. Let $r_{1},\dots,r_{m}$ be the
released requests in clockwise order from the origin. For every $q\in U$, the
left-crescent permutation of $q$ is

$(r_{1},\dots,r_{l})\ ||\ (q)\ ||\ opt_{q}((R\cup
U)\setminus\\{r_{1},\dots,r_{l}\\}),$

where $l$ is the largest index such that $r_{l}$ is to the left of $q$ in
clockwise order from the origin and $opt_{s}(S)$ denotes the fastest path
without release times that starts from $s$, visits every point in $S$ and ends
at the origin. The right-crescent permutation of $q$ is defined analogously.
We will use $lc_{R,U}(q)$ and $rc_{R,U}(q)$, respectively, to refer to these
permutations.

######  Definition 6.12 (Full-Moon Permutation).

Let $R,U$ be as in Definition 6.11 and $q\in U$. If $q$ is on the left arc of
the ring, i.e., it is encountered before the antipodal point of the origin in
a clockwise traversal of the ring, then the full-moon permutation of $q$ is

$(r_{1},\dots,r_{m})\ ||\ (q)\ ||\ opt_{q}(U).$

If $q$ is on the other arc, the order of serving the released requests is
reversed. We will use $fm_{R,U}(q)$ to refer to this permutation.

######  Definition 6.13 (Dominating Set for the Ring).

For given $R,U$ as in Definitions 6.11 and 6.12, the ring dominating set of
$R,U$ is

$Dom^{\circ}(R,U)=\bigcup_{q\in U}\\{rc_{R,U}(q),lc_{R,U}(q),fm_{R,U}(q)\\}.$

Now that we have defined the dominators, it remains to show that indeed they
dominate the sensible set of permutations which contain a loop.

######  Lemma 6.14 (Ring Domination).

Let $\pi$ be a sensible permutation whose tour contains a full loop in the
beginning. Let $t$ be the current time and $R,U$ the released and unreleased
requests at time $t$. Then, $Dom^{\circ}(R,U)$ contains a permutation
$\pi_{dom}$ which dominates $\pi$.

######  Proof 6.15.

Let $\pi=q_{1},q_{2},\dots,q_{n}$. Assume without loss of generality that
$\pi$’s loop is clockwise. Also, let $q_{x}\in U$ be the first unreleased
request in $\pi$ at time $t$. We distinguish two cases:

  * •

The request $q_{x}$ is on the loop part of $\pi$. Then, $lc_{R,U}(q_{x})\in
Dom^{\circ}(R,U)$ is a dominator for $\pi$. This is because both permutations
travel the same distance to $q_{x}$ (the clockwise arc to it) and
$lc_{R,U}(q_{x})$ serves a superset (all released request in that arc) of what
$\pi$ serves (some released requests of that arc) until this point. Also,
after reaching $q_{x}$, $lc_{R,U}(q_{x})$ optimally serves a subset of what
$\pi$ has to serve, and is thus faster on that part too, which means that it
dominates $\pi$.

  * •

The request $q_{x}$ is after the loop part of $\pi$. Then, $fm_{R,U}(q_{x})\in
Dom^{\circ}(R,U)$ is a dominator for $\pi$. This can be seen because
$fm_{R,U}(q_{x})$ serves all released requests in its loop part and moves to
$q_{x}$ after the loop at the least possible time (with cost 1 for the loop
and then the smallest arc to $q_{x}$). Thus, it serves a superset of what
$\pi$ serves until reaching $q_{x}$ in no more time than the tour induced by
$\pi$ needs. Then, it optimally serves a subset of what $\pi$ has to serve,
and is thus faster on that part too, which means that it dominates $\pi$.

Thus, our main theorem for the ring follows.

See 1.6

###  6.3 Flowers

Figure 4: A A flower with 7 petals

In this section we extend the reasoning used in the previous subsections on
rings and trees to the so-called flowers. A flower consists of a number of
rings (petals), all of which are attached to the origin point (receptacle).
For reasons of artistic completion, a semiline (stem) disjoint from the petals
is also attached to the origin point333In fact, one could do the same for
graphs which are trees plus some edge-disjoint cycles attached to a single
vertex of the tree. Thus, one can even include the flower’s (ground) roots..
An illustration is given in Figure 4. In the following, we define the sets of
sensible and dominating permutations for these kinds of graphs.

#### Sensible set.

The central idea is the following. We can assume that any sensible solution
traverses a petal of the flower in a cyclic fashion at most once, for the same
reason that this is true for the ring. Moreover, the petal is not visited
before without loss of generality. After such a traversal (if it ever occurs),
we can safely “snip” the petal in its halfpoint from the origin and view it as
two different branches of a tree, since the halfpoint will never be crossed
again. Thus, the sensible set here is defined to include the permutations
which have at most one loop for each petal, such loops are the first visit on
the corresponding petal (but may be carried out fully during any contiguous
part of the permutation) and the restrictions of the sensible set on trees
also apply to every petal (which becomes a line) after such a loop (if it even
exists) is carried out.

#### Dominating set.

Utilizing this observation, we can construct the dominating permutations as
follows. First, choose an unreleased request $q$. This will be the “current”
request of the sensible permutation for which we want to define the dominator.
Let $\pi$ refer to that permutation. Note that $\pi$, throughout its entirety,
will utilize a subset of the petals in a cyclic fashion. So, we “guess” this
subset and call it $\mathcal{P}$. Moreover, a subset $\mathcal{P}_{done}$ of
$\mathcal{P}$ will have been fully traversed before reaching $q$. We also
guess $\mathcal{P}_{done}$. This also defines
$\mathcal{P}_{left}=\mathcal{P}\setminus\mathcal{P}_{done}$. Then, the
dominator is defined in the following way. First, we traverse all petals in
$\mathcal{P}_{done}$ in an arbitrary order. Next, we “snip” every petal except
the ones in $\mathcal{P}$. This leaves us with a tree $\mathcal{T}$ (actually,
a star) and the petals in $\mathcal{P}$, which are disjoint from each other.
Note that this is safe to do if we correctly guessed the sets of petals, since
$\pi$ will behave as if it is on a tree when visiting the petals not in
$\mathcal{P}$.

Now, we also guess the subset $L^{\prime}$ of the leaves $L$ of $\mathcal{T}$
to be visited before $q$. Having fixed that, we append to our initial petal
loop subtour the optimal path from $\mathcal{O}$ to $q$ that visits every leaf
in $L^{\prime}$, and also possibly serves the arc that $\pi$ might have served
if it is currently performing a loop on $q$’s petal. Finally, we append the
optimal path from $q$ that “cleans up” the remaining unserved requests.

Note that to make all these different guesses, one has at most six choices for
every petal (loop done, loop later, or any of the 4 choices of subsets of the
two leaves after snipping). So, if the graph has $p$ petals, the cardinality
of the dominators is $O(6^{p}\cdot n)=O(2^{2.59p}\cdot n)$. The above
calculation considers the stem as a petal for simplicity. Again, this yields
an FPT algorithm for the flower case.

Here we give a proof sketch of why this works. Recall that we only need to
show that any sensible permutation $\pi$ is dominated at all times by some
dominator $\pi_{dom}$ out of the above. So, for $\pi$ at time $t$, we claim
that $\pi_{dom}$ which corresponds to the correct guess of
$q,\mathcal{P},\mathcal{P}_{done}$ and $L^{\prime}$ dominates $\pi$. Let us
first focus on the petals of $\mathcal{P}_{done}$. It is clear that
$\pi_{dom}$ serves all released requests in these petals in the least time
necessary to traverse the petals in loops, an amount of time which $\pi$ also
pays by the correct guess of $\mathcal{P}_{done}$. Now, we shift our focus
into the part of $\pi_{dom}$ after the initial loops and until reaching $q$.
By construction, it is the optimal path visiting $L^{\prime}$ and any possible
requests that $\pi$ might have served if currently on a loop traversal of
$q$’s petal. But, by a similar reasoning as in the trees subsection (the path-
extension property of the served requests of $\pi$), $\pi$ also has to
accomplish this task, independently of visiting $\mathcal{P}_{done}$ in loops.
This independence is because $L^{\prime}$ has no leaves in petals of
$\mathcal{P}_{done}$, since all released requests there are served in the
initial loops of $\pi_{dom}$ and also because in the case that $q$ is part of
a loop, its petal is not in $\mathcal{P}_{done}$. Moreover, $\pi_{dom}$ serves
all requests that $\pi$ has served until reaching $q$, since each request that
$\pi$ has served is either in a petal of $\mathcal{P}_{done}$, along a path to
a leaf in $L^{\prime}$, or along the (correctly chosen) arc to $q$. Hence,
$\pi_{dom}$ serves a superset of what $\pi$ serves and reaches $q$ at least as
fast. Domination now follows by the optimality of the “cleanup” path.

We will now make the above more formal by precisely defining the dominators
and proving that they dominate the sensible set of permutations.

######  Definition 6.16 (Hippie Permutations).

Let $R,U$ be the sets of released requests and unreleased requests at time
$t$. Let $q\in U$ be an unreleased “current” request. Let $\mathcal{P}$ be a
subset of the petals of the input flower metric space. Let
$\mathcal{P}_{done}\subseteq\mathcal{P}$. For now, let us assume that $q$ is
not on a petal of $\mathcal{P}$. Let $\mathcal{T}$ be the tree obtained by
replacing the petals not in $\mathcal{P}$ by two “branches” each with half the
length of the original petal (snip the petal at its halfpoint). $\mathcal{T}$
possibly also contains the stem of the flower. Finally, let $L$ be the leaves
of $\mathcal{T}$ (trimmed according to the released requests) and
$L^{\prime}\subseteq L$. The hippie permutations
$hp_{R,U}(q,\mathcal{P},\mathcal{P}_{done},L^{\prime})$ are defined as
follows:

  * •

First, all released requests in the petals of $\mathcal{P}_{done}$ are served
by looping through each petal once in an arbitrary way, e.g. clockwise and by
prioritizing the petals according to some fixed ordering.

  * •

Then, an optimal path is calculated which visits each leaf in $L^{\prime}$ and
ends up at $q$. We append this path (more accurately, the subpermutation
associated to it) to the permutation.

  * •

Finally, the optimal path which starts at $q$ and visits any unserved until
now request before finishing at the origin is calculated and appended.

In the case that $q$ is in a petal of $\mathcal{P}$, we slightly modify the
above definition by requiring that in the second part, not only leaves in
$L^{\prime}$ are visited but also all requests along a petal arc to $q$. We
define two such permutations, one for each arc leading to $q$. Thus,
$hp_{R,U}(q,\mathcal{P},\mathcal{P}_{done},L^{\prime})$ will refer to the set
of permutations generated in the above way (one or two permutations actually).

######  Definition 6.17 (Dominating Set for Flowers).

Let us reuse the notation of Definition 6.16. We will describe now how the
dominating set for flowers is generated. We simply take the union of the
hippie permutations for all (valid) choices of
$\mathcal{P},\mathcal{P}_{done},q,L^{\prime}$. That is, we define the set:

$Dom^{\text{{\char 80\relax}}}(R,U)=\bigcup_{\begin{subarray}{c}q\in U\\\
\text{ $\mathcal{P}$ is a subset of petals},\\\
\mathcal{P}_{done}\subseteq\mathcal{P},\\\ \text{$L^{\prime}$ is a subset of
the leaves of
$\mathcal{T}$}\end{subarray}}hp_{R,U}(q,\mathcal{P},\mathcal{P}_{done},L^{\prime})$

Finally, we can now show that the above set dominates the set of sensible
permutations for the flower.

######  Lemma 6.18 (Flower Domination).

Let $\pi$ be a sensible permutation for the flower and let $R,U$ be the
released and unreleased requests at time $t$. Then, $Dom^{\text{{\char
80\relax}}}(R,U)$ contains a permutation $\pi_{dom}$ which dominates $\pi$.

######  Proof 6.19.

Let $q$ be the first unreleased request in $\pi$ at time $t$. Also, let
$\mathcal{P}$ be the set of petals that $\pi$ will loop through (or have
already done so) at some point. Let $\mathcal{P}_{done}\subseteq\mathcal{P}$
be the subset of those which have already seen their loop completed before
reaching $q$. Let $\mathcal{T}$ be as in Definition 6.16. Let $L^{\prime}$ be
the subset of leaves that $\pi$ visits before $q$. We claim that
$hp_{R,U}(q,\mathcal{P},\mathcal{P}_{done},L^{\prime})$ contains the
permutation $\pi_{dom}$ we are looking for.

  * •

Let us assume for now that $q$ is not on a petal of $\mathcal{P}$. Then,
$hp_{R,U}(q,\mathcal{P},\mathcal{P}_{done},L^{\prime})$ is the singleton
$\\{\pi_{dom}\\}$. To see why, note that we can split the “movement” of
$\pi_{dom}$ up to $q$ into two independent parts, one for the initial loops
and one for the rest. The first part costs as much as the total length of the
petals in $\mathcal{P}_{done}$, which $\pi$ also has to pay since it has fully
looped through these petals at some point before reaching $q$. Now, notice
that none of the leaves of $L^{\prime}$ are in petals of $\mathcal{P}_{done}$,
by construction. Therefore, $\pi_{dom}$ optimally visits these leaves and
$\pi$ also has to additionally pay at least this cost (on top of and
independently of the cost associated with the loops of $\mathcal{P}_{done}$),
before reaching $q$. Therefore, we have shown that $\pi_{dom}$ follows a not
longer path until $q$. It only remains to show that with that path it serves
every request that $\pi$ has served until $q$. For the loop petals, this is
obvious, since $\pi_{dom}$ serves every released request there. Then, for all
requests outside of $\mathcal{P}$, we can view the problem as if we are on a
tree. Thus, the arguments of the tree subsection apply (closure under path-
extension etc.). It remains to show that there is no request in
$\mathcal{P}_{left}$ which $\pi$ has served but $\pi_{dom}$ has not. This is
trivial, since there is no such request because of the assumption that $q$ is
not on a petal of $\mathcal{P}_{left}$.

  * •

Now we can resolve the case where $q$ is on a loop petal. This means that
$\pi$ is currently undergoing a loop. We choose $\pi_{dom}$ to be the
permutation following the corresponding arc to $q$. The fact that $\pi_{dom}$
pays a not higher cost until reaching $q$ can be established in much the same
way (we split the costs into the first loops and then $\mathcal{T}$ plus the
final arc). The only extra thing we need to show is that $\pi_{dom}$ serves
every request in $\mathcal{P}_{left}$ that $\pi$ does until $q$. But these are
just the requests in the correctly chosen arc to $q$, and thus the claim
follows.

Again, the lemma above establishes our main theorem for flowers. As for the
trees, the complexity comes from the term related to the cardinality of the
dominating set in Lemma 3.5, since solving classical TSP on flowers is later
shown to take $O(n)$ time.

See 1.7

###  6.4 Dealing with the open variant

Much of the above analysis was based on exploiting the closed nature of the
problem, specifically the fact that $\operatorname{OPT}$ is required to return
to $\mathcal{O}$. This is no longer true in the open case. However, we can
artificially impose a similar restriction by enumerating all possible
endpoints of $\operatorname{OPT}$’s path. That is, we will assume that a
specific request $q_{f}$ will be served last by $\operatorname{OPT}$ and build
the dominating permutations under this assumption. In the end, we consider the
union of all these sets (i.e., for all choices of the final request), which
will dominate the sensible sets for the open case, since any sensible
permutation has to finish with some request.

#### Trees.

For the case of trees, this turns out to be quite simple. Once we fix $q_{f}$,
we simply need to reroot the tree at $q_{f}$. Then, all sensible permutations
which terminate at $q_{f}$ must respect the order of requests along paths to
leaves of the rerooted tree; a simplification very similar to the one we had
for the closed case. Hence, we can build the set of dominating permutations by
considering the union of tree dominators for all $n$ rerootings of the input
tree. Note that rerooting cannot increase the number of leaves by more than 1.
The cases where this happens occur only when the new root is actually along an
edge, and then we have to split that edge into two. This set dominates the
sensible set of permutations for the open case in trees and has size
$O(2^{l}\cdot n^{2})$, yielding an FPT algorithm once again.

#### Ring.

For the case of the ring, we take a different approach altogether compared to
the closed variant. Instead of specifying the sensible set and then dominating
it, we simply dominate the set of all permutations with a relatively simple
case distinction.

  * •

The first easy case is when the permutation $\pi$ to be dominated has not
crossed the point $\mathcal{O}^{\prime}$, the antipodal point of the origin
before reaching the current request $q$. In such a scenario, we view the ring
as a line and the already defined dominators for trees suffice. The
correspondence here would be that a permutation $\pi$ is dominated by the
dominator $\pi_{dom}$ which visits the same set of extreme requests (leftmost
or rightmost) as $\pi$ before $q$.

  * •

Now, let us assume that $\pi$ has indeed crossed the point
$\mathcal{O}^{\prime}$ before reaching $x$, the location of $q$. Let us be rid
of the case where $\pi$ has moved a distance of at least $1+d(x,\mathcal{O})$
before reaching request $q$, as then the permutation that serves all released
requests with a loop and then goes to $x$ as soon as possible dominates $\pi$.
Let us assume w.l.o.g. that between the last touch of $\mathcal{O}$ and the
first subsequent touch of $\mathcal{O}^{\prime}$, $\pi$ moves through the
right arc.

Now, let us focus on the left arc. Let $q_{1}$ be the request closest to
$\mathcal{O}^{\prime}$ on the left arc that $\pi$ has served before its last
visit of $\mathcal{O}$. Let $q_{2}$ be the request closest to $\mathcal{O}$ on
the left arc that $\pi$ has served after the last visit of $\mathcal{O}$ and
before leaving $q$ (it could happen that $q_{2}=q$). By $x_{1}$ and $x_{2}$,
we denote their location, respectively. Because these points have to be
traveled while moving a distance not more than $1+d(x,\mathcal{O})$, we deduce
that $d(x_{1},\mathcal{O})<d(x_{2},\mathcal{O})$. Note that no request in the
left arc of $(x_{1},x_{2})$ could have been served by $\pi$ before request
$q$.

For such $\pi$, we define the following dominator. First, $\pi_{dom}$ moves to
$x_{1}$ and serves all requests on the way back to the origin. Then, it serves
all requests along the right arc to $\mathcal{O}^{\prime}$, in that order.
After reaching $\mathcal{O}^{\prime}$, it continues moving towards $x_{2}$,
serving all requests on the way along the left arc. Finally, it moves to $x$,
after which point it optimally cleans up the still unserved requests. We see
that $\pi_{dom}$ serves all requests outside the left arc of $(x_{1},x_{2})$,
i.e., it serves a superset of what $\pi$ serves, before serving $q$. Also, the
movements of $\pi_{dom}$ can be charged independently to movements of $\pi$,
and so the distance traveled is not higher, which implies domination.

The majority of the above dominators are of the final type where we have to
choose $q,q_{1}$ and $q_{2}$ (we do not need to choose $q_{f}$ as in the case
of trees). Hence, there are $O(n^{3})$ dominators, which yields a polynomial
time algorithm.

#### Flowers.

For non-trivial flowers (i.e., not just a single ring), the situation is a bit
more complex, but we can still retrieve an FPT algorithm. Note that the final
request $q_{f}$ will either lie on a petal or not. If not, the argument that
all petals may be traversed in a cyclic fashion at most once (and not visited
at all before such a loop) still holds. Thus, simply rerooting the tree and
guessing the parameters of the closed variant flower dominators for the
modified tree (but afterwards appending the optimal solution to the open
variant) still works.

Now, if $q_{f}$ happens to lie on a petal, we have some extra work to do. Note
however that in this case, any path from a request $q$ to $q_{f}$ where $q$ is
not on the same petal as $q_{f}$ must pass through the origin. Thus, we can
still assume that the sensible permutations respect the order of requests
along paths to leaves of the (possibly snipped) tree rooted at the origin, at
least as far as requests not on the final petal are concerned. We do not
reroot the tree in such cases. Plus, all non-final petals may be traversed
cyclically at most once. We thus only have to deal with the requests on the
same petal as $q_{f}$. Fortunately, these can be dealt with relatively simply,
essentially by viewing the final petal as a single ring in the open variant.

Suppose the “current” request $q$ is not on the final petal. Then, we can deal
with the final petal with either a loop or snipping it and guessing the
leaves, as we would originally do. This is because before reaching $q$, $\pi$
will have either visited the final petal’s midpoint or not. In the first case,
it must have made a full loop, since $q$ is not on that petal. In the other,
we view the final petal as a tree.

The remaining case is the interesting one, where both $q$ and $q_{f}$ are on a
single petal. In such a case, we first guess the other petals and tree leaves
and serve them optimally in a closed manner, i.e., we return to the origin.
Now, we ignore everything but the petal of $q$ and $q_{f}$ and append a ring-
type dominator for that specific petal.

Overall, we get a dominating set whose cardinality is $O(n^{3}\cdot
6^{p})=O(n^{3}\cdot 2^{2.59p})$, where $p$ is the number of petals of the
flower. This is because we have roughly a quadratic multiplicative factor more
dominators over the closed case, since we additionally choose either $q_{f}$
or $q_{1}$ and $q_{2}$. The first case corresponds to when $q_{f}$ is on the
tree part (in which case we do not need to choose $q_{1}$ and $q_{2}$) and in
the second case the choices of $q_{1}$ and $q_{2}$ imply the choice of petal
on which $q_{f}$ is, which is all we need to know to define the ring-type
dominator we append.

###  6.5 Solving classical TSP fast

Here we describe how we compute an optimal classical TSP solution within
suitable runtime bounds. This is used in the “cleanup” step of Algorithm 2,
but also in the definition of the dominating permutations.

For trees, we can simply perform a DFS traversal (from the startpoint) while
deprioritizing the edges that lead to $q$, where $q$ is the endpoint of the
optimal path we would like to calculate. The corresponding path traced by the
DFS is optimal with cost twice the sum of edge lengths minus the length of
$q$’s path to the startpoint. Note that for our intents and purposes, we can
assume that DFS runs in $O(n)$ time, where $n$ is the number of requests. To
see this, we need to show that we can bound the size of the actual tree by a
constant multiple of $n$, since then the complexity of DFS boils down to
$O(n)$. As a first preprocessing step and only once, we do the following. We
trim the tree so that only the paths from the requests to the root (can be any
point, might as well be the origin) are retained. This means that we have
$l\leq n$, where $l$ is the number of leaves of the modified tree. Moreover,
we assume that there exists no vertex of the tree with degree exactly 2
(except possibly the origin), as these are non-essential for the OLTSP problem
(one can view the two incident edges as one). Now, notice that any vertex of
the tree has degree at least 3, except for the leaves. Let $i$ be the number
of non-leaf vertices of the tree. By the handshaking lemma, we have
$2e=\sum_{\text{$v$}}\deg(v)\geq 3i+l\implies i\leq l$, where $e$ is the
number of edges of the tree and by recalling that $e=i+l-1$. Hence, the tree
does indeed have size $O(n)$, which shows that we can solve classical TSP in
$O(n)$ time.

For flowers (which subsume the ring), we first conclude which petals are
better traversed as a cycle or as two different branches. This is easy to
decide by comparing the cost of the full cycle versus a zig-zag type traversal
that visits all requests. Afterwards, we run a DFS on the part of the flower
that is decided to be traversed as a tree and append the petal cycles at any
part of said DFS traversal where the origin is touched. The case where no such
part exists is degenerate and easily dealt with (just the semiline is
traversed by the DFS). It is easy to see that this whole procedure runs in
$O(n)$ time as well, provided we have discarded petals empty from requests as
a preprocessing step.

We note that these overheads do not matter asymptotically for LA-SWAG, since
the bottleneck of the runtime already comes from the cardinality of the
dominating sets times $n^{2}$, whereas for the computation of the dominating
permutations we only pay $O(n)$ for each and there are up to $n+1$ calls to
the domination oracle overall.

##  7 Conclusion

We studied Online TSP augmented with predictions regarding the locations of
the requests. Our algorithm, LA-SWAG, achieves a competitive ratio of $3/2$
under the assumption of perfect predictions, which is tight in most cases we
considered. Additionally, it is smooth and provides robustness guarantees
below 3, improving over previous work. The runtime of LA-SWAG is single-
exponential; however, we show how to remove the exponential dependency on the
number of requests for specific metric spaces.

We believe that our techniques can be generalized to obtain FPT algorithms for
other classes of graphs also; cactus graphs, graphs of bounded treewidth in
general, as well as planar graphs are interesting options. Additionally,
extending the algorithm to the Dial-A-Ride Problem seems like a reasonable
direction to follow. Finally, having slightly improved the consistency lower
bound in the line open variant, we conjecture that it is possible to extend
our construction and establish tightness in this case also; we suggest this as
future work.

Another interesting direction is to leverage the ideas behind the PTAS for
classical TSP on the Euclidean plane [6, 7] (or any other space which admits
an approximation scheme for that matter) to obtain consistency guarantees
which approach 3/2 arbitrarily close as the computational time is allowed to
increase. Note that, since our smoothness proof follows from consistency
itself and robustness from solving a classical TSP instance, these results
would automatically extend, modulo some worsening of the bounds as a function
of the approximation quality. For this, one possible approach is to extend the
notion of a sensible set to that of $\epsilon$-sensible, meaning that a
$(1+\epsilon)$-approximation of the optimal Online TSP solution is guaranteed
to exist within the set. A similar relaxation would also make sense for the
idea of dominating sets.

## References

  * [1] Luca Allulli, Giorgio Ausiello, and Luigi Laura.  On the power of lookahead in on-line vehicle routing problems.  In COCOON, 2005.
  * [2] Spyros Angelopoulos, Christoph Dürr, Shendan Jin, Shahin Kamali, and Marc P. Renault.  Online computation with untrusted advice.  In ITCS, 2020.
  * [3] Antonios Antoniadis, Christian Coester, Marek Eliás, Adam Polak, and Bertrand Simon.  Online metric algorithms with untrusted predictions.  In ICML, 2020.
  * [4] Antonios Antoniadis, Peyman Jabbarzade Ganje, and Golnoosh Shahkarami.  A novel prediction setup for online speed-scaling.  CoRR abs/2112.03082, 2021.
  * [5] Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev.  Secretary and online matching problems with machine learned advice.  In NeurIPS, 2020.
  * [6] Sanjeev Arora.  Polynomial time approximation schemes for euclidean TSP and other geometric problems.  In FOCS, 1996.
  * [7] Sanjeev Arora.  Nearly linear time approximation schemes for euclidean TSP and other geometric problems.  In FOCS, 1997.
  * [8] Norbert Ascheuer, Martin Grötschel, Sven O. Krumke, and Jörg Rambau.  Combinatorial online optimization.  In Peter Kall and Hans-Jakob Lüthi, editors, Operations Research Proceedings 1998, pages 21–37, Berlin, Heidelberg, 1999. Springer Berlin Heidelberg.
  * [9] Giorgio Ausiello, Marc Demange, Luigi Laura, and Vangelis Paschos.  Algorithms for the on-line quota traveling salesman problem.  Inf. Process. Lett., 92(2):89–94, 2004.
  * [10] Giorgio Ausiello, Esteban Feuerstein, Stefano Leonardi, Leen Stougie, and Maurizio Talamo.  Algorithms for the on-line travelling salesman.  Algorithmica, 29:560–581, 2001.
  * [11] Étienne Bamas, Andreas Maggiori, Lars Rohwedder, and Ola Svensson.  Learning augmented energy minimization via speed scaling.  In NeurIPS, 2020.
  * [12] Étienne Bamas, Andreas Maggiori, and Ola Svensson.  The primal-dual method for learning augmented algorithms.  In NeurIPS, 2020.
  * [13] Evripidis Bampis, Bruno Escoffier, Niklas Hahn, and Michalis Xefteris.  Online TSP with Known Locations.  To appear in WADS, 2023.  CoRR abs/2210.14722.
  * [14] Evripidis Bampis, Bruno Escoffier, and Michalis Xefteris.  Canadian traveller problem with predictions.  In Parinya Chalermsook and Bundit Laekhanukit, editors, Approximation and Online Algorithms, pages 116–133, Cham, 2022. Springer International Publishing.
  * [15] Richard Bellman.  Dynamic programming treatment of the travelling salesman problem.  J. ACM, 9(1):61–63, Jan 1962.
  * [16] Giulia Bernardini, Alexander Lindermayr, Alberto Marchetti-Spaccamela, Nicole Megow, Leen Stougie, and Michelle Sweering.  A universal error measure for input predictions applied to online graph problems.  In NeurIPS, 2022.
  * [17] Antje Bjelde, Jan Hackfeld, Yann Disser, Christoph Hansknecht, Maarten Lipmann, Julie Meißner, Miriam Schlöter, Kevin Schewior, and Leen Stougie.  Tight bounds for online TSP on the line.  ACM Trans. Algorithms, 17(1):3:1–3:58, 2021.
  * [18] Michiel Blom, Sven O. Krumke, Willem E. De Paepe, and Leen Stougie.  The online TSP against fair adversaries.  INFORMS J. Comput., 13(2):138–148, 2001.
  * [19] Shuchi Chawla and Dimitris Christou.  Online time-windows TSP with predictions.  CoRR, abs/2304.01958, 2023.  arXiv:2304.01958, doi:10.48550/arXiv.2304.01958.
  * [20] Paul Dütting, Silvio Lattanzi, Renato Paes Leme, and Sergei Vassilvitskii.  Secretaries with advice.  In EC, 2021.
  * [21] Franziska Eberle, Alexander Lindermayr, Nicole Megow, Lukas Nölke, and Jens Schlöter.  Robustification of online graph exploration methods.  Proceedings of the AAAI Conference on Artificial Intelligence, 36(9):9732–9740, Jun. 2022.
  * [22] Sreenivas Gollapudi and Debmalya Panigrahi.  Online algorithms for rent-or-buy with expert advice.  In ICML, 2019.
  * [23] Themis Gouleakis, Konstantinos Lakis, and Golnoosh Shahkarami.  Learning-Augmented Algorithms for Online TSP on the Line.  To appear in AAAI, 2023.  CoRR abs/2206.00655.
  * [24] Michael Held and Richard M. Karp.  A dynamic programming approach to sequencing problems.  J. Soc. Indust. Appl. Math., 10(1):196–210, 1962.
  * [25] Hsiao-Yu Hu, Hao-Ting Wei, Meng-Hsi Li, Kai-Min Chung, and Chung-Shou Liao.  Online TSP with predictions.  CoRR, abs/2206.15364, 2022.
  * [26] Patrick Jaillet and Michael R. Wagner.  Online routing problems: Value of advanced information as improved competitive ratios.  Transportation Science, 40:200–210, 05 2006.
  * [27] Vinay A. Jawgal, V. N. Muralidhara, and P. S. Srinivasan.  Online travelling salesman problem on a circle.  In T.V. Gopal and Junzo Watada, editors, Theory and Applications of Models of Computation, pages 325–336, Cham, 2019. Springer International Publishing.
  * [28] Murali Kodialam and T. V. Lakshman.  Prediction augmented segment routing.  In 2021 IEEE 22nd International Conference on High Performance Switching and Routing (HPSR), pages 1–6, 2021.
  * [29] Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, and Neoklis Polyzotis.  The case for learned index structures.  In SIGMOD, 2018.
  * [30] Eugene L. Lawler, Jan K. Lenstra, Alexander H. G. Rinnooy Kan, and David B. Shmoys.  The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization.  Wiley Series in Discrete Mathematics & Optimization, 1991.
  * [31] Alexander Lindermayr and Nicole Megow.  Alps.  https://algorithms-with-predictions.github.io/.
  * [32] Thodoris Lykouris and Sergei Vassilvitskii.  Competitive caching with machine learned advice.  J. ACM, 68(4):24:1–24:25, 2021.
  * [33] Michael Mitzenmacher.  A model for learned bloom filters and optimizing by sandwiching.  In NeurIPS, 2018.
  * [34] Michael Mitzenmacher.  Scheduling with predictions and the price of misprediction.  In ITCS, 2020.
  * [35] Michael Mitzenmacher and Sergei Vassilvitskii.  Algorithms with predictions.  In Beyond the Worst-Case Analysis of Algorithms. Cambridge University Press, 2020.
  * [36] Benjamin Moseley, Sergei Vassilvitskii, Silvio Lattanzi, and Thomas Lavastida.  Online scheduling via learned weights.  In SODA, 2020.
  * [37] Harilaos N. Psaraftis, Marius M. Solomon, Thomas L. Magnanti, and Tai-Up Kim.  Routing and scheduling on a shoreline with release times.  Manag. Sci., 36(2):212–223, 1990.
  * [38] Manish Purohit, Zoya Svitkina, and Ravi Kumar.  Improving online algorithms via ml predictions.  In NeurIPS, 2018.
  * [39] Dhruv Rohatgi.  Near-optimal bounds for online caching with machine learned advice.  In SODA, 2020.
  * [40] Shufan Wang and Jian Li.  Online algorithms for multi-shop ski rental with machine learned predictions.  In AAMAS, 2020.
  * [41] Alexander Wei.  Better and simpler learning-augmented online caching.  In APPROX/RANDOM, 2020.

##  Appendix A Consistency lower bound on the line for the open case

######  Proposition A.1.

No algorithm can have a better consistency than $\frac{1+\sqrt{61}}{6}$ for
open LA-OLTSP on the line.

######  Proof A.2.

Let $\lambda=\frac{1+\sqrt{61}}{6}\approx 1.468$, which satisfies
$\lambda=\frac{5}{3\lambda-1}$.

Let $A$, $O$, $B$ be the points on the line with coordinates $x_{A}=-1$,
$x_{O}=0$ and $x_{B}=1$. We consider that we have a continuous set of requests
between $A$ and $B$ (this can be easily discretized to get the same asymptotic
lower bound with a finite number of request). None are released until $t=1$.
Let also denote $\delta=5-3\lambda$ (note that $\delta$ is slightly larger
than 0.5).

We consider two cases at $t=1$. Let $s$ denote the position of the algorithm
at $t=1$. We assume w.l.o.g. that $s\geq 0$.

If $s\geq 1-\delta$, then we release all the requests at unit speed, starting
at $A$ at $t=1$ till $B$ at $t=3$. Then $|OPT|=3$. If the algorithm serves $B$
before $A$, it needs at least 5. If it serves $A$ before $B$, it needs at
least $1+(1-\delta)+1+2=3\lambda$. Hence, the competitive ratio is at least
$\lambda$.

Otherwise, $0\leq s<1-\delta$. Then we release the requests from $A$ and from
$B$ at unit speed, until the first time $t_{0}$ such that the algorithm is at
some position $s^{\prime}$ with $|s^{\prime}|=(2-t_{0})-\delta$, i.e., the
server is at distance $\delta$ from the “released part” of the requests. We
distinguish two cases, depending on $t_{0}$. We assume w.l.o.g. that
$s^{\prime}\geq 0$ at $t_{0}$, so $s^{\prime}=(2-t_{0})-\delta$. Let $C$ and
$D$ be the points at positions $x_{C}=-(2-t_{0})$ and $x_{D}=2-t_{0}$,
respectively (i.e., at $t_{0}$ the requests are released on $[A,C]$ and on
$[D,B]$).

  * •

If $t_{0}\geq 3\lambda-3$ (intuitively slightly less than half of the requests
are released, and  is close to $O$), then we release the requests from $C$ to
$D$ at unit speed, starting at $t_{0}$. Then again $|OPT|=3$. If  serves $A$
before $B$, as previously it needs
$t_{0}+(2-t_{0}-\delta)+3=5-\delta=3\lambda$. If  serves $B$ before $A$, it
needs $t_{0}+(1-(2-t_{0}-\delta))+2=2t_{0}+\delta+1=2t_{0}+6-3\lambda\geq
3\lambda$. The competitive ratio is at least $\lambda$.

  * •

Finally, if $t_{0}\leq 3\lambda-3=2-\delta$ (intuitively,  is not “too close”
to the origin): we release at $t_{0}$ all the requests but the one in $D$.
Then intuitively either  went towards $A$, and we will act as previously. Or
it went towards $B$, and we will block the release in $D$. More formally, at
$t=t_{0}+1$:

    * –

if the algorithm is at a position $s^{\prime\prime}<0$, then we release the
last request (in $D$). Note that  cannot have served $A$ (as we had
$s^{\prime}>0$ at $t_{0}$) nor $B$ (no time to have $s^{\prime\prime}<0$ at
$t_{0}+1$). Then, the best  can do after $t=t_{0}+1$ is to go to $A$ (as
$s^{\prime\prime}<0$), and then to $B$. As we had
$s^{\prime}=(2-t_{0})-\delta$ at $t_{0}$, we have $|$, while
$|\operatorname{OPT}|=3$, so the competitive ratio is at least $\lambda$.

    * –

if $s^{\prime\prime}\geq 0$, we release the last request in $D$ at
$t_{1}=3+(1-x_{D})=2+t_{0}$. Then $|\operatorname{OPT}|=t_{1}$ (be in $A$ at
time 1, then go to $B$ (time 3) and back to $D$). If  serves $A$ before $D$,
as $s^{\prime\prime}\geq 0$ at $t_{0}+1$, it needs at least
$t_{0}+1+2+x_{D}=5$. If it serves $D$ before $A$, as $D$ is released at
$t_{1}$, it needs at least $t_{1}+x_{D}+1=5$. Hence, the competitive ratio is
at least $\frac{5}{t_{1}}=\frac{5}{t_{0}+2}\geq\frac{5}{3\lambda-1}=\lambda$
(by definition of $\lambda$).