# Orienteering problem with time-windows
and updating delay

Marc Demange<EMAIL_ADDRESS>David Ellison
<EMAIL_ADDRESS>Bertrand Jouve<EMAIL_ADDRESS>RMIT
University, School of Science, Melbourne, Australia  LISST UMR5193, Toulouse
University, CNRS, France

###### Abstract

The Orienteering Problem with Time Window and Delay (OPTiWinD) is a variant of
the online orienteering problem. A series of requests appear in various
locations while a vehicle moves within the territory to serve them. Each
request has a time window during which it can be served and a weight which
describes its importance. There is also a minimum delay $T$ between successive
requests. The objective is to find a path for the vehicles that maximises the
sum of the weights of the requests served. We further assume that the length
of each time window is equal to the diameter of the territory. We study the
optimal performance and competitive ratio for the set of instances with $n$
requests. We obtain complete resolution for $T$ at least half of the diameter,
small values of $T$ or small values of $n$, as well as partial results in the
remaining cases.

Keywords — Online orienteering problem, Online Scheduling, Competitive
analysis, Combinatorial optimisation.

##  1 Introduction and related work

###  1.1 Defining the problem

This work is motivated by a wildfire emergency management problem. On very hot
days and during the dry season, in regions exposed to wildfires, it is not
rare to observe, in a single region, up to one hundred fire ignitions per day.
Some of these fires spread very quickly and, if not extinguished quickly, they
escape and become completely out of control. Although the risk factors, such
as temperature, wind, fuel load, dryness, etc. and the main causes of ignition
are well-understood, it is almost impossible to forecast, during a day, where
and when a fire will occur. Wildfires are already an important threat to human
lives, goods and the environment; and in the near future, this is expected to
become worse due to climate change.

For emergency management commanders, one of the main challenges is to rely on
efficient decision making. And when disaster strikes, especially when
fatalities occur, they need to be able to justify their decisions once the
crisis is over. Hence, in order to satisfy legal constraints, the decision
chain needs to be very clear and well-defined. The most critical decision
commanders need to make during the initial outbreak is the allocation of
firefighting resources in cases where there are not enough resources to keep
all the fires under control. Such a decision relies on the information
available about the on-going fires and the threats they pose. Early warning
systems are set-up to detect new fires, but once a smoke plume has been
detected, an on-site reconnaissance is necessary to assess the importance of
the fire, evaluate the possible induced risk and estimate how long until the
fire can no longer be contained. Based on this information, the management
team decides whether or not to send firefighting resources to each new fire.
Given that making this decision requires having evaluated all the risks
associated with the fire, each new fire is only taken into account after a
delay corresponding to the time used by the reconnaissance team. We will
assume that there is a single firefighter team which cannot be divided, thus
two fires igniting simultaneously will be processed one at a time with a delay
between them. Natural generalisations may induce several or splittable teams.
The objective is to schedule the movements of the team by selecting which
fires to extinguish and when, in order to maximise the total weight of the
fires contained. We model this situation using a sequence of fires, each with
a weight representing the expected loss if the fire goes out of control and a
time window in which the fire has been assessed and remains controllable. We
include a minimum delay between the release time of fires.

This model corresponds to the standard Orienteering Problem in a space $X$,
with Time Windows and with the addition of time delays. This variant will be
called The Orienteering Problem with Time Window and Delay (OPTiWinD). In this
problem, time is continuous and new requests can appear at any moment and at
any point in $X$. Each request has a location, a weight and a time window
during which it can be served. There is a minimum delay between successive new
requests. The player controls a unique vehicle which travels to serve the
requests. A request is instantaneously satisfied when it is visited. The
player’s objective is to find a path in the space that maximises the sum of
the weights of the requests served. A strategy of the player is described as
an algorithm.

We will consider online algorithms for instances where each request is
revealed at the start of its time window. This corresponds to the reality of
our motivating problem, for which the difficulty to establish firefighting
strategies is largely due to not knowing in advance when and where the fires
will appear.

###  1.2 Related work

The underlying combinatorial optimisation problem is a natural generalisation
of the Metric Travelling Salesman Problem (Metric TSP), which is also called
the _Orienteering Problem_ [6]: one is given a time limit and a graph with $n$
vertices including departure and arrival points. Each vertex is associated
with a score and each edge with a distance. The objective is to select some
vertices and an order to visit them while travelling at constant speed 1 from
the departure point to the arrival point, so that the time limit is not
exceeded and the total score of visited vertices is maximised. In Laporte and
Martello, [9], the orienteering problem is called _Selective TSP_. The same
problem has been studied under other names, in particular _Bank Robber
Problem_ [3] and _Maximum Collection Problem_. The dual problem where the aim
is to collect a fixed targeted total score in the minimum time is called
_Quota TSP_ [3] or also _Prize Collecting Problem_. These problems fall into
the class of _Travelling Salesman Problems with Profits_ [5]. Our application
deals with the version of the orienteering problem with time windows [10]:
instead of an overall time limit, each vertex is associated with a release
time and a deadline and it must be visited between these two dates in order to
collect the associated score.

Some of these problems have been considered in the online case, also referred
as _dynamic case_. In most cases, the online setup consists in revealing
requests (vertices) over time, so that the online algorithm needs to decide
about the movements of the vehicle without knowing when and where the next
request will be revealed. The Metric Travelling Salesman has been considered
under this setup in [1, 2], for instance, and the Quota TSP in [1]. When the
delay is zero, OPTiWinD is equivalent to the _Whack-a-Mole Problem_ , which is
defined in Gutiérrez et al., [7], or the _Dynamic Traveling Repair Problem_
[8]. For a space which is a truncated line $[-L,L]$, Gutiérrez et al., [7]
note that the only non trivial cases are those for $\theta/4<L\leq\theta$,
where $\theta$ denotes the size of the time windows. Thus, they study the case
$\theta=L$ with moles that may only arrive at integer positions on $[-L,L]$.
In the case of the segment, we study in this paper the case where
$L=\theta/2$, which is not examined in Gutiérrez et al., [7]. To our
knowledge, no previous paper deals with a delay between requests.

##  2 Preliminaries

###  2.1 Geodesic metric spaces

A metric space $E=(X,d)$ is said to be _geodesic_ [4] if for any $a,b\in X$,
there is a continuous path $\gamma:[0,1]\rightarrow X$ from $a$ to $b$ such
that the range of $\gamma$ is isometric to the segment $[0,d(a,b)]$.

Defining the offline orienteering problem on graphs or on metric spaces is
equivalent. The distance, or travel time, between requests is the only aspect
of the underlying metric space relevant to the game. However, in the online
case, the position of the vehicle must be defined at all time. Hence the
online orienteering problem is defined either on graphs (e.g. [8]) or on
geodesic metric spaces (e.g. [2]), producing two slightly different online
games.

Having a geodesic metric space means that the distance between two points is
equal to the length of the shortest path connecting them. The vehicle is
allowed to change directions whenever a new request appears, even when the
vehicle is travelling between requests. Alternatively, on graphs, the vehicle
can only select a new direction after reaching a vertex.

###  2.2 Definitions and notations

For geodesic metric spaces with only one pair of points maximising the
distance, it is natural to consider a worst case scenario when all the
requests appear on these two points. As it happens, the case where $E$ is a
segment is critical to understanding the general case. Thus, except in Section
8, we will consider the online problem on the segment $[-1,1]$ with the
vehicle starting at $0$. We will show in Section 8 that most of the results
for the segment can be extended to bounded geodesic metric spaces of diameter
2, and we will give counter-examples to the others.

An instance of OPTiWinDis a set of requests, each characterised by a triple
$(A,[r,r^{\prime}],\delta)$ where $A\in X$ is the location of the request, $r$
is the release time, $r^{\prime}$ is the time when the request is lost if it
is not served and $\delta\in\mathbb{R}_{+}^{*}$ is the _weight_ (or score)
associated with the request.

A request $(A,[r,r^{\prime}],\delta)$ is said to be _served_ if the vehicle is
on $A$ at a time $t\in[r,r^{\prime}]$. A feasible solution is an itinerary for
the vehicle starting at $O$ at time $t=0$ and serving some requests. The
objective is to maximise the total weight of the requests served. We denote by
$\mathcal{I}_{n,T}$ the set of instances of OPTiWinD on $[-1,1]$ with at most
$n$ requests and delay at least $T$ between requests.

We will make the following assumptions about the OPTiWinD Problem:

  * •

We consider that $X$ is the segment $[-1,1]$, except in Section 8 where we
extend the problem to the case of a bounded geodesic metric space $X$ of
diameter 2.

  * •

The vehicle is able to move no faster than unit speed in $X$ and a request is
instantaneously satisfied when it is visited.

  * •

We assume that each time window is of the form $[r,r+2]$ where $r$ is the
release time. Thus, once a request appears, the vehicle always has a chance to
reach its location in time from anywhere in $E$.

  * •

The release times of any two successive requests differ by at least a delay
$T\geq 0$, which is independent from the requests.

  * •

Online algorithms for OPTiWinD learn about a new request (its location and
weight) at the start of its associated time window. The vehicle can serve it
at any time within that time window or it can choose not to serve it at all.
The geodesic metric space is completely known from the beginning.

In the following, the sets of non-negative integers and real numbers are
denoted by $\mathbb{N}$ and $\mathbb{R}$ respectively. The golden ratio is
$\varphi$. The $i$-th request is denoted $f_{i}$ and its release time is
$t_{i}$. The weight of $f_{i}$ is $\delta_{i}$ and
$S_{i}=\sum_{k=1}^{i}\delta_{k}$. The earliest time when the vehicle may reach
$f_{i}$, assuming it starts heading towards it at $t_{i}$, is $\tau_{i}$.

###  2.3 Performance and competitive ratio

The _performance_ $\lambda_{ALG}^{I}$ of an algorithm $ALG$ for an instance
$I\in\mathcal{I}_{n,T}$ of OPTiWinD is the ratio of the sum of the weights of
the served requests by the total sum of the weights of all requests. The
performance of $ALG$ for at most $n$ requests and delay $T$ is then defined
as:

$\lambda_{ALG}^{\mathcal{I}_{n,T}}=\inf_{I\in\mathcal{I}_{n,T}}\lambda_{ALG}^{I}.$

By definition, any $\lambda_{ALG}^{I}$ is in $[0,1]$; hence
$\lambda_{ALG}^{\mathcal{I}_{n,T}}\in[0,1]$. An online algorithm $ALG$ is
$\gamma$-competitive for problem OPTiWinD with at most $n$ requests and delay
$T$ if, given any instance $I\in\mathcal{I}_{n,T}$, the performance of the
online algorithm is at least $\gamma$ multiplied by the performance of $OPT$,
the optimal offline algorithm: $\forall I\in\mathcal{I}_{n,T}$,
$\lambda_{ALG}^{I}\geq\gamma\cdot\lambda_{OPT}^{I}$, with $\gamma>0$. Note
that this definition of competitive ratio is standard for maximisation
problems. Hence, we have $0\leq\gamma\leq 1$. The _c_ ompetitive ratio of
$ALG$ for at most $n$ requests and delay $T$ is defined by:

$\gamma_{ALG}^{\mathcal{I}_{n,T}}=\inf_{I\in\mathcal{I}_{n,T}}\frac{\lambda_{ALG}^{I}}{\lambda_{OPT}^{I}}.$

For any algorithm $ALG$, we have
$\lambda_{ALG}^{\mathcal{I}_{n,T}}\leq\gamma_{ALG}^{\mathcal{I}_{n,T}}$. In
order to evaluate the performance and competitive ratio of an algorithm, we
need to consider a worst case scenario. This situation corresponds to having a
malicious adversary deciding when the requests are released and choosing their
weights. While our problem is a one-player online game, as the adversary is
not technically a player, it is standard practice to discuss strategies of the
adversary as though in a two-player game.

The _optimal performance_ and the _optimal competitive ratio_ are
respectively:

$\lambda^{\mathcal{I}_{n,T}}=\sup_{ALG}\lambda_{ALG}^{\mathcal{I}_{n,T}}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \mathrm{and}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
\gamma^{\mathcal{I}_{n,T}}=\sup_{ALG}\gamma_{ALG}^{\mathcal{I}_{n,T}}$

An online algorithm will be called _optimal_ if its competitive ratio is equal
to the optimal competitive ratio. Note that we have:

$\lambda^{\mathcal{I}_{n,T}}\leq\gamma^{\mathcal{I}_{n,T}}.$

######  Definition 1.

Given a function $f:\mathbb{N}\rightarrow\mathbb{R}^{+}$, we say that an
online algorithm $ALG$ is $f(n)$-performant (resp. $f(n)$-competitive) if it
guarantees a performance (resp. competitive ratio) of $f(n)$ for instances
with $n$ requests. Hence:

$\lambda_{ALG}^{\mathcal{I}_{n,T}}\geq f(n)\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ (\mathrm{resp.}\leavevmode\nobreak\
\gamma_{ALG}^{\mathcal{I}_{n,T}}\geq f(n)).$

Note that in Definition 1, the algorithm functions without knowing ahead of
time the total number of requests that will appear.

######  Proposition 1.

The functions $\lambda^{\mathcal{I}_{n,T}}$ and $\gamma^{\mathcal{I}_{n,T}}$
are non-decreasing with respect to $T$ and non-increasing with respect to $n$.

###### Proof.

Increasing $T$ restricts the strategy of the adversary without affecting the
player’s algorithm. Similarly, increasing $n$ increases the possibilities for
the adversary. More precisely, if $T\leq T^{\prime}$, then
$\mathcal{I}_{n,T^{\prime}}\subset\mathcal{I}_{n,T}$ and if $n\leq
n^{\prime}$, then $\mathcal{I}_{n,T}\subset\mathcal{I}_{n^{\prime},T}$. ∎

######  Remark 1.

In order to find bounds to performances and competitive ratios, we may
restrict our analysis by omitting inefficient algorithms. It is inefficient
for the vehicle to slow down or to change directions when no request appears.
Thus we will assume that the vehicle always moves at speed 1 and with a
constant direction between the release times $t_{i}$ and $t_{i+1}$ of two
successive requests.

######  Remark 2.

Multiplying all the weights $\delta_{i}$ by a positive constant does not
affect the game. Thus we will always suppose that the weight of the first
request is $\delta_{1}=1$, except in the proof of Theorem 2.

###  2.4 Summary of results

The optimal performance and competitive ratio are both decreasing with the
number of requests $n$. For a fixed $n$, they are non-decreasing step
functions with regards to the delay $T$. We distinguish three cases
corresponding to small, large or medium delays. The following results were
obtained for the case where $X$ is the segment $[-1,1]$.

  * •

When there is no delay, there is a natural greedy algorithm for the vehicle
which consists in always heading towards the request of greatest weight. This
greedy algorithm is optimal, guaranteeing a performance and a competitive
ratio of $\frac{1}{n}$. Small delays refer to values of $T$ small enough that
this greedy algorithm remains optimal. This means
$T<T_{0}=\frac{1}{2^{n-3}+1}$ in terms of performance and
$T<T_{1}=\frac{1}{2^{n-1}-2}$ in terms of competitive ratio.

  * •

With a delay $T$ greater or equal to 1, a more refined greedy algorithm,
defined in Section 4, becomes optimal. The values of the optimal performances
and optimal competitive ratios are then defined by a sequence $(\alpha_{n})$
which is analysed in the appendix.

  * •

The intermediate case is the most complex and remains mostly open. When the
delay $T$ reaches the critical value $T_{0}$ (resp. $T_{1}$), the performance
(resp. competitive ratio) increases by at least
$\epsilon=\frac{1}{n(n-1)(n+3)}$. For $\frac{1}{2}\leq T<1$, the performance
is characterised by a sequence $(\beta_{n})$, which is difficult to compute
beyond the first few terms.

Delay | Performance | Competitive Ratio
---|---|---
$T<T_{1}$ |  $\frac{1}{n}$ (**) |  $\frac{1}{n}$ (**)
$T_{1}\leq T<T_{0}$ |  $\frac{1}{n}$ (**) | $>\frac{1}{n}$
$T_{0}\leq T<\frac{1}{2}$ | $\geq\frac{1}{n}+\epsilon$ | $\geq\frac{1}{n}+\epsilon$
$\frac{1}{2}\leq T<1$ |  $\beta_{n}$ (*) |  $\geq\beta_{n}$ (*)
$1\leq T<2-\frac{1}{n-1}$ |  $\alpha_{n-\lfloor\frac{1}{2-T}\rfloor}$ (*) |  $\alpha_{n-\lfloor\frac{1}{2-T}\rfloor}$ (*)
$2-\frac{1}{n-1}\leq T$ | 1 (*) | 1 (*)
Table 1: Performances and Competitive Ratios with $T_{0}=\frac{1}{2^{n-3}+1}$,
$T_{1}=\frac{1}{2^{n-1}-2}$, $\epsilon=\frac{1}{n(n-1)(n+3)}$. The results
marked with an asterisk (resp. a double asterisk) can be generalised to
centred geodesic metric spaces (resp. geodesic metric spaces) of diameter 2.

These general results are summarised in Table 1. In sections 3 to 6, we study
successively the performances and competitive ratios for no delay, large
delays, small delays and medium delays on the segment $[-1,1]$. Section 7
deals with values of $n\leq 4$, whence we are able to calculate explicitly the
performance and competitive ratios for all the possible values of the delay.
Results for $n=3$ and $n=4$ are summarised in Tables 2 and 3. In Section 8, we
generalise previous results to the case of centred geodesic metric spaces of
diameter 2 (indicated with an asterisk in Table 1) or more generally to
geodesic metric spaces of diameter 2 (indicated with a double asterisk).
_Centred_ geodesic metric spaces of diameter $2$ are spaces included in
$\overline{B}(O,1)$, where $\overline{B}(O,1)$ is the closed ball of radius
$1$ centred in $O$.

Delay | Performance | Competitive Ratio
---|---|---
$T<1/2$ | $1/3$ | $1/3$
$1/2\leq T<1$ | $1/\varphi^{2}\approx 0.3820$ | $1/\varphi^{2}\approx 0.3820$
$1\leq T<1.5$ | $1/2$ | $1/2$
$1.5\leq T$ | 1 | 1
Table 2: Performances and Competitive Ratios for 3 requests ($n=3$) Delay | Performance | Competitive Ratio
---|---|---
$T<1/6$ | $1/4$ | $1/4$
$1/6\leq T<1/5$ | $0.2578$
$1/5\leq T<1/4$ | $2-\sqrt{3}\approx 0.2679$
$1/4\leq T<1/3$ | $0.2803$
$1/3\leq T<1/2$ | $2-\sqrt{3}\approx 0.2679$ | $1-\sqrt{2}/2\approx 0.2929$
$1/2\leq T<1$ | $1-\sqrt{2}/2\approx 0.2929$ | $0.3177$
$1\leq T<1.5$ | $1/\varphi^{2}\approx 0.3820$ | $1/\varphi^{2}\approx 0.3820$
$1.5\leq T<5/3$ | $1/2$ | $1/2$
$5/3\leq T$ | 1 | 1
Table 3: Performances and Competitive Ratios for 4 requests ($n=4$)

##  3 OPTiWinD with no Delay

In this section, we will show that a greedy algorithm is optimal when there is
no delay, and that no online algorithm guarantees a constant competitive
ratio.

We consider a greedy algorithm for the vehicle, denoted by $GR_{0}$, in which
the vehicle always moves towards the request of greatest weight. Thus,
whenever a new request appears with a greater weight, the vehicle ignores his
previous destination to go towards the new one.

######  Lemma 1.

The algorithm $GR_{0}$ is $\frac{1}{n}$-performant; i.e.
$\lambda_{GR_{0}}^{\mathcal{I}_{n,0}}=\frac{1}{n}$.

###### Proof.

By applying $GR_{0}$, the vehicle is guaranteed to serve the request of
greatest weight. This is sufficient to ensure a performance at least equal to
$1/n$. ∎

Note that it follows from Lemma 1 that $GR_{0}$ is $\frac{1}{n}$-competitive.

######  Theorem 1.

For instances of $\mathcal{I}_{n,0}$, the algorithm $GR_{0}$ is optimal; i.e.
$\gamma^{\mathcal{I}_{n,0}}=\frac{1}{n}$

###### Proof.

Let us consider an online algorithm $ALG$ for the vehicle. We will describe a
strategy of the adversary which limits the competitive ratio of $ALG$ to
$\frac{1}{n}$. The adversary first releases a request $f_{1}=(-1,[1,3],1)$. If
the vehicle does not go towards $-1$, the adversary will not release any more
requests, and the performance will be $0$. Thus, we may assume that the
vehicle will start moving towards $-1$ at time $1$. The strategy of the
adversary is as follows: let $\tau_{1}$ be the estimated time arrival (ETA) of
the vehicle, i.e. $\tau_{1}=2$. While the vehicle maintains his course and
fewer than $n$ requests have been released, the adversary releases requests

$f_{1,k}=(1,[\tau_{1}-\frac{1}{4.3^{k}.n},\tau_{1}-\frac{1}{4.3^{k}.n}+2],1)\,,\,\,k\geq
0.$

If at time $\tau_{1}-\frac{1}{4.3^{k}.n}$, the vehicle changes directions to
go towards $1$, the adversary sets $\tau_{2}$ as the new ETA in 1. He then
repeats the process, with

$f_{i,k}=((-1)^{i+1},[\tau_{i}-\frac{1}{4.3^{k}.n},\tau_{i}-\frac{1}{4.3^{k}.n}+2],1)$

where $\tau_{i}$ is the ETA in $(-1)^{i}$ after the vehicle’s $i$-th change of
directions, until $n$ requests have been released (see Figure 1 for an
illustration). In this manner, a total of exactly $n$ requests will be
released. Also, when request $f_{i,k}$ is released, if $k>0$, it is already
too late for the vehicle to reach $f_{i,k-1}$. Thus the vehicle will serve
only one request. Note that $2i-\frac{i}{2n}\leq\tau_{i}\leq 2i$. Hence,
$2i-\frac{1}{2}\leq\tau_{i}\leq 2i$. So
$2i+1\in[\tau_{i}-\frac{1}{4.3^{k}.n},\tau_{i}-\frac{1}{2.3^{k}.n}+2]$. Hence,
an optimal offline algorithm will serve all the requests by starting at $t=0$
towards $-1$ and reaching $(-1)^{i+1}$ at time $2i+1$. Thus, no algorithm can
guarantee a competitive ratio greater than $\frac{1}{n}$.

$t=1$-1$f_{1},f_{2,0}$1$f_{1,0},f_{1,1}$$2-\epsilon$$2-\epsilon/3$$4-5\epsilon/3$

Figure 1: Initial movements of the vehicle in the case where it changes
direction toward $f_{1,1}$ at time $2-\epsilon/3$. Using $\epsilon=1/4n$, the
figure displays the vehicle’s position at each release time

.

∎

######  Remark 3.

When a new request $f_{i}$ is released at time $t_{i}$, if $\tau_{i}$ denotes
the ETA for reaching $f_{i}$, then, given that the vehicle moves at speed $1$,
the distance to $f_{i}$ at $t_{i}$ is $\tau_{i}-t_{i}$.

Also, if the vehicle moves away from $f_{i}$ towards $f_{k}$ at time $t_{i}$,
when the vehicle has passed half the distance to $f_{k}$, it is too late to
serve $f_{i}$. Thus, if a request $f_{i+1}$ is released at the same end as
$f_{i}$, it is impossible to serve both $f_{i}$ and $f_{i+1}$ if and only if
$\tau_{k}-t_{i+1}<\frac{1}{2}(\tau_{k}-t_{i})$.

######  Remark 4.

Note that Theorem 1 implies that there is no algorithm with a constant
competitive ratio for OPTiWinD with zero delay.

##  4 OPTiWinD with Large Delays

In this section, we will show that introducing a large delay significantly
improves the performance and competitive ratio. The result shown in Theorem 1
indicates that the previous case is extremely unfavorable to the vehicle.
However, this changes when we impose a delay between the release times of
successive requests. With a delay sufficiently large, the strategy of the
adversary used in the proof of Theorem 1 is no longer possible. Indeed, this
strategy required that requests be released in rapid succession in $-1$ and
$1$.

Let us note that if $T\geq 2$ then $GR_{0}$ will serve all the requests. So,
the only interesting case is when $T<2$. For $n\geq 1$, we define:

$\alpha_{n}=\inf\limits_{\delta\in(\mathbb{R}_{+}^{*})^{n}}\max\\{\frac{\delta_{1}}{S_{2}},\cdots,\frac{\delta_{i}}{S_{i+1}},\cdots,\frac{\delta_{n-1}}{S_{n}},\frac{\delta_{n}}{S_{n}}\\}$

where $S_{i}=\sum_{k=1}^{i}\delta_{k}$. (See Appendix for the study of
$(\alpha_{n})$.)

######  Theorem 2.

For $1\leq T\leq 2-\frac{1}{n-1}$, we have
$\lambda^{\mathcal{I}_{n,T}}=\gamma^{\mathcal{I}_{n,T}}=\alpha_{n-\lfloor\frac{1}{2-T}\rfloor}$
and for $T\geq 2-\frac{1}{n-1}$,
$\lambda^{\mathcal{I}_{n,T}}=\gamma^{\mathcal{I}_{n,T}}=1$.

###### Proof.

First, we will give a strategy of the adversary with a parameter $\epsilon>0$
which limits the competitive ratio to
$\alpha_{n-\lfloor\frac{1}{2-T}\rfloor}+O(\epsilon)$, when
$\epsilon\rightarrow 0$. Then, we will give a greedy algorithm for the vehicle
which guarantees a performance of $\alpha_{n-\lfloor\frac{1}{2-T}\rfloor}$.

  1. 1.

Let $\epsilon>0$. The strategy of the adversary is defined as follows:

    1. (a)

First, release a request $f_{1}=(-1,[1,3],\epsilon)$.

    2. (b)

If the vehicle does not serve $f_{1}$, do not release any more requests.

    3. (c)

Similarly, while the vehicle serves all the requests up to $f_{i-1}$ and
$i\leq i_{0}=\lfloor\frac{1}{2-T}\big{\rfloor}$, release a request

$f_{i}=((-1)^{i},[1+(i-1)T,3+(i-1)T],4^{i-1}\epsilon).$

    4. (d)

If the vehicle serves $f_{i_{0}}$, release a request

$f_{i_{0}+1}=((-1)^{i_{0}+1},[1+i_{0}T,3+i_{0}T],1).$

    5. (e)

Then, while the vehicle does not serve any more requests and $i\leq n$,
release a request

$f_{i}=((-1)^{i},[2i-2-\eta_{i},2i-\eta_{i}],\delta_{i-i_{0}})$

where $(\delta_{i})$ realises $\alpha_{n-\lfloor\frac{1}{2-T}\rfloor}$ (see
appendix) and $\eta_{i}=\frac{i-i_{0}}{n}-\frac{3}{2n}$.

    6. (f)

When the vehicle serves a request $f_{i}$, $i>i_{0}$, do not release any more
requests.

Note that $\forall i\leq i_{0}+1$, $2i-1\in[1+(i-1)T,3+(i-1)T]$. Since
$i_{0}\geq 1$, we have $\eta_{i}\leq\eta_{n}\leq 1-\frac{5}{2n}<1$. So,
$\forall i\geq i_{0}+2$, $2i-1\in[2i-2-\eta_{i},2i-\eta_{i}]$. Therefore, the
optimal offline algorithm will serve all the requests by being in $(-1)^{i}$
at time $2i-1$. Also, the values of $\eta_{i}$ have been chosen so that for
$i\geq i_{0}+2$, $t_{i}=\tau_{i-1}-\frac{1}{2n}$.

Let us now consider an online algorithm, $ALG$. When the adversary uses the
above strategy, if $ALG$ does not allow the vehicle to serve $f_{i}$ for
$i\leq i_{0}$, then the performance is
$\frac{\sum\limits_{k=1}^{i-1}4^{k-1}\epsilon}{\sum\limits_{k=1}^{i}4^{k-1}\epsilon}=\frac{4^{i-1}-1}{4^{i}-1}<\frac{1}{4}$.
It is shown in Proposition 8 in the appendix that
$\frac{1}{4}<\alpha_{n-\lfloor\frac{1}{2-T}\rfloor}$.

If $ALG$ allows the vehicle to serve the first $i_{0}$ requests, the vehicle
will then reach at most one $f_{i}$ with $i>i_{0}$. Its performance will then
be

$\displaystyle\frac{\delta_{i-i_{0}}+\sum\limits_{k=1}^{i_{0}}4^{k-1}\epsilon}{\sum\limits_{k=1}^{i-i_{0}+1}\delta_{k}+\sum\limits_{k=1}^{i_{0}}4^{k-1}\epsilon}$
$\displaystyle=$
$\displaystyle\frac{\delta_{i-i_{0}}}{S_{i-i_{0}+1}}+O(\epsilon)$
$\displaystyle=$
$\displaystyle\alpha_{n-\lfloor\frac{1}{2-T}\rfloor}+O(\epsilon).$

Therefore,
$\gamma^{\mathcal{I}_{n,T}}\leq\alpha_{n-\lfloor\frac{1}{2-T}\rfloor}$.

  2. 2.

The greedy algorithm $GR_{1}$ is defined as follows:

    1. (a)

When there is no request to be served, or none that can be reached in time,
head towards $0$.

    2. (b)

While a single request that can be served is ongoing, head towards it.

    3. (c)

When a request $f_{2}=(x_{2},[t_{2},t_{2}+2],\delta_{2})$ is released while
another request $f_{1}=(x_{1},[t_{1},t_{1}+2],\delta_{1})$ is still reachable,
if
$\frac{\delta_{1}}{\delta_{1}+\delta_{2}}\geq\alpha_{n-\lfloor\frac{1}{2-T}\rfloor}$,
head towards $f_{1}$; else head towards $f_{2}$. From this point on, until a
request is served, number the requests $f_{1}$ to $f_{d}$ and denote by
$\delta_{i}$ the weight of $f_{i}$ and $S_{i}=\sum_{k=1}^{i}\delta_{k}$. When
$f_{i+1}$ is released, if
$\frac{\delta_{i}}{S_{i+1}}\geq\alpha_{n-\lfloor\frac{1}{2-T}\rfloor}$, head
towards $f_{i}$; else, head towards $f_{i+1}$.

We will divide the game into phases according to when the vehicle is either in
cases a) and b) or in case c).

In the phases corresponding to a) and b), the vehicle will serve all the
requests, and the performance over those phases of the game will be $1$.

If at some point during the game, a sequence of requests $f_{1},\ldots,f_{d}$
places the vehicle in case c), we will show that the performance will be
greater or equal to $\alpha_{n-\lfloor\frac{1}{2-T}\rfloor}$ over this phase.
With a delay of $T$ and the vehicle applying algorithm $GR_{1}$, the first
time case c) may occur is for the $(i_{0}+1)$-th and $(i_{0}+2)$-th requests,
where $i_{0}=\lfloor\frac{1}{2-T}\big{\rfloor}$. Hence, $d\leq n-i_{0}$. Note
that when a request $f_{i}=(x_{i},[t_{i},t_{i}+2],\delta_{i})$ is served at
time $t$, since $T\geq 1$ and the time windows have length $2$, at most one
request may have been released between $t_{i}$ and $t$. It follows that when
$f_{i}$ is reached, the performance over that phase of the game is
$\frac{\delta_{i}}{S_{i}}$ or $\frac{\delta_{i}}{S_{i+1}}$. By definition of
$(\alpha_{n})$, this performance is at least $\alpha_{n-i_{0}}$.

Hence, in all phases of the game, the performance is at least
$\alpha_{n-\lfloor\frac{1}{2-T}\rfloor}$. Therefore,
$\lambda_{ALG}^{\mathcal{I}_{n,T}}\geq\alpha_{n-\lfloor\frac{1}{2-T}\rfloor}$.

It follows from 1. and 2. that we have
$\lambda^{\mathcal{I}_{n,T}}=\gamma^{\mathcal{I}_{n,T}}=\alpha_{n-\lfloor\frac{1}{2-T}\rfloor}$
for $1\leq T\leq 2-\frac{1}{n-1}$.

Hence,
$\lambda^{\mathcal{I}_{n,2-\frac{1}{n-1}}}=\gamma^{\mathcal{I}_{n,2-\frac{1}{n-1}}}=\alpha_{1}=1$.
Therefore, for $T\geq 2-\frac{1}{n-1}$, we have
$\lambda^{\mathcal{I}_{n,T}}=\gamma^{\mathcal{I}_{n,T}}=1$.

∎

##  5 OPTiWinD with Small Delays

In this section, we will consider cases where $T$ is small enough that the
results from Section 3 still apply.

######  Theorem 3.

For $T<T_{0}=\frac{1}{2^{n-3}+1}$, we have
$\lambda^{\mathcal{I}_{n,T}}=\frac{1}{n}$.

###### Proof.

When the vehicle has to choose between two symmetrically placed requests of
equal weights and cannot serve both, it is optimal to go towards the closest
one. We will restrict our description of the strategy of the adversary by
assuming that the vehicle follows this rule.

The strategy of the adversary is to release requests

$f_{i}=(-1,[t_{i},t_{i}+2],1)$

where $t_{1}=1$, $t_{i}=2-\frac{1-T}{2^{i-2}}+\frac{1-T}{2^{n-2}}-\frac{T}{2}$
for $2\leq i\leq n-1$, and $t_{n}=t_{n-1}+T$. Note that
$T<\frac{1}{2^{n-3}+1}$ implies $T<\frac{1-T}{2^{n-3}}$. Hence,
$t_{i+1}-t_{i}\geq T$ for all $1\leq i\leq n-1$.

Let us show by induction that if the player follows the rule given at the
beginning of this proof, starting from $t=1$, the vehicle will always move
towards $-1$. This is true when the request $f_{1}$ appears. Let us assume
that it moved towards $-1$ until $f_{i+1}$ appears. Thus, when $f_{i+1}$ is
released, the vehicle is located at $1-t_{i+1}$. Hence, the distance between
its current position and $1$ is $t_{i+1}$. Note that for $2\leq i\leq n-1$, we
have
$\frac{1}{2}(2-t_{i})=\frac{1-T}{2^{i-1}}-\frac{1-T}{2^{n-1}}-\frac{T}{4}>2-t_{i+1}$.
Hence, $2t_{i+1}>t_{i}+2$. Therefore, when $f_{i+1}$ is released, it is too
late to serve $f_{i}$. Thus, the vehicle will continue towards $-1$.

So, this strategy is well defined for optimal play. Also, the vehicle will
only be able to serve a single request, and $n$ requests will be released.
Hence, the performance is at most $\frac{1}{n}$. Since the algorithm $GR_{0}$
guarantees at least $\frac{1}{n}$, we have an equality. ∎

######  Theorem 4.

For $n\geq 3$ and $T<T_{1}=\frac{1}{2^{n-1}-2}$, the algorithm $GR_{0}$ is
optimal and $\gamma^{\mathcal{I}_{n,T}}=\frac{1}{n}$.

###### Proof.

Let us consider an online algorithm $ALG$ for the vehicle. We will describe a
strategy of the adversary which limits the competitive ratio of $ALG$ to
$\frac{1}{n}$. The adversary first releases a request $f_{1}=(-1,[1,3],1)$. If
the vehicle does not go towards $-1$, the adversary will not release any more
requests, and the performance will be $0$. Thus, we may assume that the
vehicle will start moving towards $-1$ at time $1$. The strategy of the
adversary is as follows:

  1. 1.

let $\tau_{1}$ be the estimated time arrival (ETA) of the vehicle in $-1$,
i.e. $\tau_{1}=2$.

  2. 2.

While the vehicle maintains its course and fewer than $n-1$ requests have been
released, the adversary releases requests

$f_{1,k}=(1,[\tau_{1}-2^{n-3-k}(T+2\epsilon)+\epsilon,\tau_{1}-2^{n-3-k}(T+2\epsilon)+\epsilon+2],1)$

for $0\leq k\leq n-3$ and some $0<\epsilon<T$.

  3. 3.

If at time $\tau_{1}-2^{n-3-k}(T+2\epsilon)+\epsilon$, the vehicle chooses to
change directions to go towards $1$, the adversary sets $\tau_{2}$ as the new
ETA in 1.

  4. 4.

He then repeats the process, with

$f_{i,k}=((-1)^{i+1},[\tau_{i}-2^{n-2-i-k}(T+2\epsilon)+\epsilon,\tau_{i}-2^{n-2-i-k}(T+2\epsilon)+\epsilon+2],1)$

where $\tau_{i}$ is the ETA in $(-1)^{i}$ after the vehicle’s $i$-th change of
directions, until $n-1$ requests have been released.

In this manner, a total of exactly $n-1$ requests will be released. If the
vehicle changed directions $j-1$ times in total, the $n$-th request will be

$f_{n}=((-1)^{j+1},[\tau_{j}-\epsilon,\tau_{j}-\epsilon+2],1).$

We will show that a) this strategy satisfies the condition regarding the delay
$T$, b) the vehicle can only serve a single request and c) for $\epsilon$
small enough the optimal offline algorithm can serve all the requests.

  1. a)

Note that the delay between $f_{i,k}$ and $f_{i,k+1}$ is greater than $T$
(even $T+2\epsilon$), and the delay between $f_{n}$ and $f_{j,k}$, for the
last value of $k$, is at least $T$.

  2. b)

When request $f_{i,k}$ is released, if $k>0$, it is already too late for the
vehicle to reach $f_{i,k-1}$. Similarly, when $f_{n}$ is released, it is too
late to serve $f_{j,k}$. Thus the vehicle will serve only one request.

  3. c)

If the vehicle changes direction when $f_{i,0}$ is released, the new ETA in
$(-1)^{i+1}$ is $\tau_{i}+2-2^{n-1-i}(T+2\epsilon)+2\epsilon$. Hence,

$\tau_{i+1}\geq\tau_{i}+2-2^{n-1-i}(T+2\epsilon)+2\epsilon=\tau_{i}+2-2^{n-1-i}T+O(\epsilon).$

Therefore, we have $\tau_{i}\geq 2i-(2^{n-1}-2^{n-i})T+O(\epsilon)$. Thus, the
time window of $f_{i,k}$ closes at

$\tau_{i}-2^{n-2-i-k}T+2+O(\epsilon)\geq
2i+2-(2^{n-1}-2^{n-i}-2^{n-2-i-k})T+O(\epsilon).$

Since $2^{n-i}+2^{n-2-i-k}>2$, we have $(2^{n-1}-2^{n-i}-2^{n-2-i-k})T<1$.
Hence, for $\epsilon$ small enough, $2i+1$ is in the time window of $f_{i,k}$.
Similarly, the time window of $f_{n}$ closes at

$\tau_{j}-\epsilon+2+O(\epsilon)\geq 2j+2-(2^{n-1}-2^{n-j})T+O(\epsilon)\geq
2j+2-(2^{n-1}-2)T+O(\epsilon).$

Hence, for $\epsilon$ small enough, $2j+1$ is in the time window of $f_{n}$.
Therefore, the optimal offline algorithm will serve all the requests by
starting at $t=0$ towards $-1$ and reaching $(-1)^{i+1}$ at time $2i+1$.

Thus no algorithm can obtain a competitive ratio greater than $\frac{1}{n}$. ∎

##  6 OPTiWinD with Medium Delays

###  6.1 Tightness of the bounds $T_{0}$ and $T_{1}$

In this section, we will show that when the delay $T$ is at least $T_{0}$
(resp. $T_{1}$), the optimal performance (resp. competitive ratio) is greater
than $\frac{1}{n}$, meaning that the boundaries $T_{0}$ and $T_{1}$ are tight.

In order to show that the boundary $T_{0}$ is tight, we will use the following
lemma, inspired by the proof of Theorem 3.

######  Lemma 2.

Let $T\geq\frac{1}{2^{n-3}+1}$. Starting at time 1, if the vehicle, initially
at 0, always moves towards the request $f_{1}=(-1,[1,3],\delta_{1})$, and if
$n-1$ other requests are released before time 2, there will be a moment when
the vehicle has the possibility of serving two requests.

###### Proof.

Since the vehicle is moving towards $-1$, we may assume that the other $n-1$
requests are all located in $1$; thus we will use the same notations as in the
proof of Theorem 3. The earliest possible release time for $f_{2}$ is $1+T$.
For $2\leq i\leq n-1$,

  * •

if $2-t_{i+1}\geq\frac{1}{2}(2-t_{i})$, it follows from Remark 3 that it is
possible for the vehicle to serve both $f_{i}$ and $f_{i+1}$.

  * •

if $2-t_{i+1}<\frac{1}{2}(2-t_{i})$, then $t_{n-1}>2-T$. Thus, $t_{n}>2$; and
it is possible to serve both $f_{1}$ and $f_{n}$.

∎

######  Theorem 5.

For $T_{0}=\frac{1}{2^{n-3}+1}$, we have
$\lambda^{\mathcal{I}_{n,T_{0}}}\geq\frac{1}{n}+\epsilon$, where
$\epsilon=\frac{1}{n(n-1)(n+3)}$.

###### Proof.

We define the algorithm $Al1$ as follows:

  1. (a)

When the first request $f_{1}$ is released, head towards it. We may assume
that $f_{1}=(-1,[1,3],1)$.

  2. (b)

While no weight is greater than $\kappa=\frac{1+n\epsilon}{1-n(n-1)\epsilon}$
and the vehicle does not have the possibility of serving two requests, keep
going towards $f_{1}$.

  3. (c)

If a request $f_{i}$ appears with weight $\delta_{i}>\kappa$, head towards it
and behave like $GR_{0}$ from this point onwards.

  4. (d)

If at some point the vehicle has the possibility of serving two requests,
combine their weights and behave like $GR_{0}$.

We will show that
$\lambda_{Al1}^{\mathcal{I}_{n,T_{0}}}\geq\frac{1}{n}+\epsilon$.

\- Case (b): If no weight is greater than $\kappa$ and the vehicle never has
the possibility of serving two requests, it will reach $f_{1}$ at time $2$. It
follows from Lemma 2 that at most $n-1$ requests have been released at this
point. Therefore, the vehicle’s performance is at least
$\frac{1}{\kappa(n-1)}$. Note that with $\epsilon=\frac{1}{n(n-1)(n+3)}$, we
have

$\frac{1}{\kappa(n-1)}=\frac{1-n(n-1)\epsilon}{1+n\epsilon}\frac{1}{n-1}=\frac{1}{n}\frac{n^{2}+2n}{n^{2}+2n-2}>\frac{1}{n}\frac{n^{2}+2n-2}{n^{2}+2n-3}=\frac{1}{n}+\epsilon.$

\- Case (c): If $\delta_{1}=1$ and
$\delta_{i}>\frac{1+n\epsilon}{1-n(n-1)\epsilon}$, we cannot have both
$\max(\delta_{i})\leq(\frac{1}{n}+\epsilon)S_{n}$ and
$\min(\delta_{i})\geq(\frac{1}{n}-(n-1)\epsilon)S_{n}$. And since
$\max(\delta_{i})\leq(\frac{1}{n}+\epsilon)S_{n}$ implies
$\min(\delta_{i})\geq(\frac{1}{n}-(n-1)\epsilon)S_{n}$, we have:
$\frac{\max(\delta_{i})}{S_{n}}>\frac{1}{n}+\epsilon$.

\- Case (d): Let us assume that, at time $t_{j}$, the vehicle becomes able to
serve two requests of weights $\delta_{i}$ and $\delta_{j}$. Let
$\Delta=\\{1,\ldots,n+1\\}-\\{i,j\\}$ and let
$\delta_{n+1}=\delta_{i}+\delta_{j}$. Let $J=\\{1\leq k\leq
j|f_{k}\leavevmode\nobreak\ \mathrm{is\leavevmode\nobreak\
no\leavevmode\nobreak\ longer\leavevmode\nobreak\
reachable\leavevmode\nobreak\ at\leavevmode\nobreak\ time}\leavevmode\nobreak\
t_{j}\\}$ and let $\delta=\max_{k\in\Delta-J}\delta_{k}$. We define
$S_{\Delta}=\sum_{k\in\Delta}\delta_{k}$ and $S_{J}$ similarly. Note that when
the possibility of serving two requests appears at time $t_{j}$, the request
$f_{1}$ is still reachable. Hence, $1\notin J$ and $\delta\geq 1$. Also, since
we are in case (d), $\forall k\in J$, $\delta_{k}\leq\kappa$. By behaving like
$GR_{0}$, the vehicle is sure to serve a request of weight at least $\delta$.
As $\kappa>1$, we have:

$S_{\Delta}\leq(n-1-|J|)\delta\leq\kappa\delta(n-1-|J|)\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\ S_{J}\leq\kappa|J|\leq\kappa\delta|J|.$

Hence, the vehicle’s optimal performance is at least equal to:

$\frac{\delta}{S_{n}}=\frac{\delta}{S_{\Delta}+S_{J}}\geq\frac{1}{\kappa(n-1)}>\frac{1}{n}+\epsilon.$

∎

######  Corollary 1.

We have $\lambda^{\mathcal{I}_{n,T}}=\frac{1}{n}$ if and only if
$T<\frac{1}{2^{n-3}+1}$.

###### Proof.

This follows directly from Theorem 3, Theorem 5 and the fact that
$\lambda^{\mathcal{I}_{n,T}}$ increases with $T$. ∎

In order to prove that the bound given in Theorem 4 is tight, we define the
algorithm $Al2$ as follows:

  1. (a)

When $f_{1}$ is released at $t_{1}=1$ in $-1$, go towards $-1$.

  2. (b)

When $f_{2}$ is released at $t_{2}$ in $1$, if $t_{2}>2-2^{n-3}T_{1}$, keep
going towards $-1$ either until two requests can be served by changing
direction, or until $f_{1}$ is reached; else go towards $1$ and set $\tau_{2}$
as the ETA in $1$.

  3. (c)

Similarly, while the vehicle has changed direction with each new request, when
$f_{i}$ is released at $t_{i}$ in $(-1)^{i}$, if
$t_{i}>\tau_{i-1}-2^{n-1-i}T_{1}$, keep going towards $(-1)^{i-1}$ either
until two requests can be reached by changing direction, or until $f_{i-1}$ is
reached; else change direction towards $(-1)^{i}$ and set $\tau_{i}$ as the
ETA in $(-1)^{i}$.

######  Lemma 3.

For $n\geq 3$ and given a delay $T\geq T_{1}=\frac{1}{2^{n-1}-2}$, the
algorithm $Al2$ guarantees that if $n$ requests are released, either the
vehicle can serve at least two requests or no optimal offline algorithm can
serve all requests.

###### Proof.

We may assume that the first request released by the adversary is
$f_{1}=(-1,[1,3],1)$ and the vehicle applies $Al2$. Assuming it exists, let
$i$ denote the smallest index for which $t_{i}>\tau_{i-1}-2^{n-1-i}T$. The
vehicle will keep going towards $(-1)^{i-1}$. For $i\leq k\leq n-1$, if
$\tau_{i-1}-t_{k+1}\geq\frac{1}{2}(\tau_{i-1}-t_{k})$, then it follows from
Remark 3 that the vehicle can serve both $f_{k}$ and $f_{k+1}$. However, if
$\tau_{i-1}-t_{k+1}<\frac{1}{2}(\tau_{i-1}-t_{k})$, for all $i\leq k\leq n-1$,
then $\tau_{i-1}-t_{n-1}<T$ so the $n$-th request cannot be released before
$f_{i-1}$ is reached.

Since $\forall i\geq 2$, $\tau_{i}=2t_{i}-\tau_{i-1}+2$, if $\forall 2\leq
i\leq n-1$, $t_{i}\leq\tau_{i-1}-2^{n-1-i}T$, then

$\tau_{n-1}\leq\tau_{1}+2(n-2)-\sum_{i=1}^{n-2}2^{i}T\leq\tau_{1}+2(n-2)-\sum_{i=1}^{n-2}2^{i}T_{1}=2n-3.$

So if $t_{n}<\tau_{n-1}$, then $2n-1\notin[t_{n},t_{n}+2]$. Hence, either the
vehicle can serve two requests, or the optimal offline algorithm cannot serve
all the requests. ∎

######  Theorem 6.

For $T_{1}=\frac{1}{2^{n-1}-2}$, we have
$\gamma^{\mathcal{I}_{n,T_{1}}}>\frac{1}{n}$.

###### Proof.

Let $0<\epsilon<\frac{1}{n^{2}}$,
$\kappa=\frac{1+n\epsilon}{1-n(n-1)\epsilon}$ and let the sequence
$(\omega_{i})$ be defined by $\omega_{1}=1$ and
$\omega_{i+1}=\omega_{i}(1-n^{2}\epsilon)-(i-2)(\kappa-\omega_{i})$. We define
the algorithm $Al3$ as follows:

  1. (a)

When $f_{1}=(-1,[1,3],1)$ is released and while each request $f_{i}$ has a
weight satisfying $\omega_{i}\leq\delta_{i}\leq\kappa$ and no two requests can
be served, apply $Al2$.

  2. (b)

If the request $f_{i}$ has a weight $\delta_{i}>\kappa$ or
$\delta_{i}<\omega_{i}$, apply $GR_{0}$.

  3. (c)

If two requests can be served, combine them and apply $GR_{0}$.

We will show that for $\epsilon$ small enough, $Al3$ guarantees a competitive-
ratio of $\frac{1}{n}+\epsilon$.

We can show by induction that $\omega_{i}\leq 1$ and
$\omega_{i}=1+O(\epsilon)$. Since $\kappa>1\geq\omega_{i}$, we have
$(\omega_{i})$ is decreasing. Note also that $\kappa=1+O(\epsilon)$, so
$\frac{\omega_{i}}{\kappa}=1+O(\epsilon)$.

\- Case (a): Assume that for all $i$, $\omega_{i}\leq\delta_{i}\leq\kappa$ and
no two requests can ever be served. Then, the vehicle applies $Al2$ until the
end. It follows from Lemma 3 that the optimal offline algorithm will not be
able to serve $n$ requests. Thus the competitive ratio in this case is at
least $\frac{\omega_{n}}{(n-1)\kappa}=\frac{1}{n-1}+O(\epsilon)$. Hence, for
$\epsilon$ small enough, this competitive ratio is greater than
$\frac{1}{n}+\epsilon$.

\- Case (b.1): Assume now that the vehicle switches from $Al2$ to $GR_{0}$
when a request $f_{i}$ is released with $\delta_{i}>\kappa$. This case is
identical to Case (c) in the proof of Theorem 5. Thus, the performance is at
least $\frac{1}{n}+\epsilon$.

\- Case (b.2): Assume now that the vehicle switches from $Al2$ to $GR_{0}$
when a request $f_{i}$ has a weight $\delta_{i}<\omega_{i}$. Let $j$ denote
the index of the request towards which the vehicle was heading when $f_{i}$
was released. Let $\delta=\max\\{\delta_{k},k>i\\}\cup\\{\delta_{j}\\}$. The
vehicle will at least serve a request of weight $\delta$, with
$\delta\geq\omega_{i-1}$ and $\delta_{i}<\omega_{i}$. The sum of the weights
is at most $(n-i+1)\delta+\delta_{i}+(i-2)\kappa$. So the competitive ratio is
at least

$\displaystyle\frac{\delta}{(n-i+1)\delta+\delta_{i}+(i-2)\kappa}\geq\frac{\omega_{i-1}}{(n-i+1)\omega_{i-1}+\omega_{i}+(i-2)\kappa}$
$\displaystyle\geq$
$\displaystyle\frac{\omega_{i-1}}{(n-i+1)\omega_{i-1}+\omega_{i-1}(1-n^{2}\epsilon)+(i-2)\omega_{i-1}}$
$\displaystyle\geq$ $\displaystyle\frac{1}{n-n^{2}\epsilon}$
$\displaystyle\geq$ $\displaystyle\frac{1}{n}+\epsilon.$

\- Case (c): Assume now that the vehicle switches from $Al2$ to $GR_{0}$ when
two requests can be served. This case is similar to Case (d) of the proof of
Theorem 5. The only difference is that we no longer have $\delta\geq 1$. Using
the same notations, we have instead $\delta\geq\omega_{j-1}$. Thus the
performance is at least $\frac{\omega_{j-1}}{\kappa(n-1)}$. For $\epsilon$
small enough, this is greater than $\frac{1}{n}+\epsilon$.

Hence, for $\epsilon$ small enough, $Al3$ guarantees a competitive ratio of
$\frac{1}{n}+\epsilon$. ∎

We close this section by showing that the optimal performance for
$\frac{1}{2}\leq T<1$ can be expressed using an induction formula. In order to
solve the general case for $\frac{1}{2}\leq T<1$, we introduce a variant
problem in which the initial state is modified. Thus we define the _optimal_
weighted performance $\lambda^{\mathcal{I}_{n,T},\delta_{0}}$ as the optimal
performance obtained by an algorithm in the case where the vehicle’s starting
position at $t=0$ is somewhere in $]T-1,1-T[$, requests with a total weight of
$\delta_{0}\geq 0$ have already been missed and the next request to appear is
of weight $1$. We will show that this is well defined as the optimal weighted
performance does not depend on where in $]T-1,1-T[$ the vehicle starts.

######  Theorem 7.

For $\frac{1}{2}\leq T<1$, the optimal weighted performance
$\lambda^{\mathcal{I}_{n,T},\delta_{0}}$ satisfies the following:

  * •

$\lambda^{\mathcal{I}_{1,T},\delta_{0}}=\frac{1}{1+\delta_{0}}\;\;$ and
$\;\;\lambda^{\mathcal{I}_{2,T},\delta_{0}}=\frac{1}{2+\delta_{0}}$,

  * •

$\forall n\geq 3$,

$\displaystyle\lambda^{\mathcal{I}_{n,T},\delta_{0}}$ $\displaystyle=$
$\displaystyle\inf\limits_{\delta_{2}\geq
0}\max\\{\frac{1}{\delta_{0}+1+\delta_{2}},\min\\{\lambda^{\mathcal{I}_{n-2,T},\frac{\delta_{0}+1+\delta_{2}}{\delta_{2}}},$
$\displaystyle\lambda^{\mathcal{I}_{n-1,T},\frac{\delta_{0}+1}{\delta_{2}}}\\}\\}.$

###### Proof.

If $n=1$, the vehicle will reach the request of weight $1$, so its performance
will be $\frac{1}{1+\delta_{0}}$. If $n=2$, the vehicle will always be able to
reach one of the two requests, and the worst case is when both requests are
released with delay $T$ at opposite ends and with equal weights. In that case,
the vehicle’s performance is $\frac{1}{2+\delta_{0}}$. Let us now consider
$n\geq 3$. We may assume that the first request is $f_{1}=(-1,[0,2],1)$ and
that the vehicle will move towards it. After a delay of at least $T$ and
before $f_{1}$ is served, the adversary will release a request
$f_{2}=(1,[t_{2},t_{2}+2],\delta_{2})$. The vehicle will thus have two
options. If it continues towards the first request, it will serve $f_{1}$
before a third request can be released and its performance will be
$\frac{1}{\delta_{0}+1+\delta_{2}}$. If it changes direction towards $f_{2}$,
it will have returned to the interval $]T-1,1-T[$ at time $t_{2}+T$. While the
vehicle remains in this interval, the adversary may release a request
$f_{3}=(-1,[t_{3},t_{3}+2],\delta_{3})$, and the vehicle will have to choose
between $f_{2}$ and $f_{3}$. In this case, it follows from the symmetry of
that situation that it is optimal for the adversary to select
$\delta_{3}=\delta_{2}$. If we divide all the weights by $\delta_{2}$, the
situation is identical to that of the problem defined above, with $n$ replaced
by $n-2$ and $\delta_{0}$ replaced by
$\frac{\delta_{0}+1+\delta_{2}}{\delta_{2}}$. While the vehicle is in the
interval $]T-1,1-T[$, the adversary may choose not to release a request, and
similarly, in this case, $n$ is replaced by $n-1$ and $\delta_{0}$ is replaced
by $\frac{\delta_{0}+1}{\delta_{2}}$. Hence,

$\displaystyle\lambda^{\mathcal{I}_{n,T},\delta_{0}}$ $\displaystyle=$
$\displaystyle\inf\limits_{\delta_{2}\geq
0}\max\\{\frac{1}{\delta_{0}+1+\delta_{2}},\min\\{\lambda^{\mathcal{I}_{n-2,T},\frac{\delta_{0}+1+\delta_{2}}{\delta_{2}}},$
$\displaystyle\lambda^{\mathcal{I}_{n-1,T},\frac{\delta_{0}+1}{\delta_{2}}}\\}\\}.$

∎

######  Corollary 2.

For $\frac{1}{2}\leq T<1$, we have $\lambda^{\mathcal{I}_{n,T}}=\beta_{n}$,
where $\beta_{1}=1$, $\beta_{2}=\frac{1}{2}$ and $\forall n\geq 3$,

$\beta_{n}=\inf\limits_{\delta_{2}\geq
0}\max\\{\frac{1}{1+\delta_{2}},\min\\{\lambda^{\mathcal{I}_{n-2,T},\frac{1+\delta_{2}}{\delta_{2}}},\lambda^{\mathcal{I}_{n-1,T},\frac{1}{\delta_{2}}}\\}\\}.$

###### Proof.

It follows from the definitions that the optimal performance
$\lambda^{\mathcal{I}_{n,T}}$ is equal to the optimal weighted performance
$\lambda^{\mathcal{I}_{n,T},0}$ with zero requests missed. ∎

######  Conjecture 1.

The formulas in Theorem 7 and Corollary 2 can be simplified as follows: for
all $\frac{1}{2}\leq T<1$ and $n\geq 3$,

$\lambda^{\mathcal{I}_{n,T},\delta_{0}}=\inf\limits_{\delta_{2}\geq
0}\max\\{\frac{1}{\delta_{0}+1+\delta_{2}},\lambda^{\mathcal{I}_{n-2,T},\frac{\delta_{0}+1+\delta_{2}}{\delta_{2}}}\\}$
$\text{and}\leavevmode\nobreak\
\;\;\;\lambda^{\mathcal{I}_{n,T}}=\inf\limits_{\delta_{2}\geq
0}\max\\{\frac{1}{1+\delta_{2}},\lambda^{\mathcal{I}_{n-2,T},\frac{1+\delta_{2}}{\delta_{2}}}\\}.$

In the proof of Proposition 2 below, we verify that for $n=3$ or $4$, we have
$\lambda^{\mathcal{I}_{n-2,T},\frac{\delta_{0}+1+\delta_{2}}{\delta_{2}}}\leq\lambda^{\mathcal{I}_{n-1,T},\frac{\delta_{0}+1}{\delta_{2}}}$.
Using Proposition 2, we can easily verify that it is also true for $n=5$. So
the conjecture is true for small values of $n$. The conjecture states that it
is inefficient for the adversary to pass on the possibility of releasing a
request when the vehicle comes back near $0$.

Table 4 summarises the results obtained so far:

Delay | Performance | Competitive Ratio
---|---|---
$T<T_{1}$ | $\frac{1}{n}$ | $\frac{1}{n}$
$T_{1}\leq T<T_{0}$ | $\frac{1}{n}$ | $>\frac{1}{n}$
$T_{0}\leq T<\frac{1}{2}$ | $\geq\frac{1}{n}+\epsilon$ | $\geq\frac{1}{n}+\epsilon$
$\frac{1}{2}\leq T<1$ | $\beta_{n}$ | $\geq\beta_{n}$
$1\leq T<2-\frac{1}{n-1}$ | $\alpha_{n-\lfloor\frac{1}{2-T}\rfloor}$ | $\alpha_{n-\lfloor\frac{1}{2-T}\rfloor}$
$2-\frac{1}{n-1}\leq T$ | 1 | 1
Table 4: Performances and Competitive Ratios with
$T_{0}=\frac{1}{2^{n-3}+1},T_{1}=\frac{1}{2^{n-1}-2}$,
$\epsilon\leavevmode\nobreak\ =\leavevmode\nobreak\ \frac{1}{n(n-1)(n+3)}$.

The performance remains unknown for $T_{0}\leq T<\frac{1}{2}$, and the
competitive ratio for $T_{1}\leq T<1$.

##  7 OPTiWinD with a total number of requests at most $4$

In this section, we will give a complete description of what happens when the
number of requests is at most $4$.

When there is only one request, the vehicle can always reach it, so the
performance and competitive ratio are equal to 1.

When the number of requests is at most two, the performance and competitive
ratio are equal to $\frac{1}{2}$ if $T<1$ and $1$ otherwise.

For $n=3$, the cases $T<\frac{1}{2}$ and $T\geq 1$ are covered by Theorem 4
and Theorem 2, respectively. The case $\frac{1}{2}\leq T<1$ is given as an
induction formula in Theorem 7. In the following proposition, we calculate the
induction formula for $n=3$ and $n=4$.

######  Proposition 2.

For $\frac{1}{2}\leq T<1$, we have
$\lambda^{\mathcal{I}_{3,T},\delta_{0}}=\frac{2}{3+\delta_{0}+\sqrt{\delta_{0}^{2}+2\delta_{0}+5}}$
and
$\lambda^{\mathcal{I}_{4,T},\delta_{0}}=\frac{2}{4+\delta_{0}+\sqrt{\delta_{0}^{2}+8}}$.

###### Proof.

Using the formulas given in Theorem 7, we obtain:

$\lambda^{\mathcal{I}_{3,T},\delta_{0}}=\inf\limits_{\delta_{2}\geq
0}\max\big{\\{}\frac{1}{\delta_{0}+1+\delta_{2}},\frac{1}{1+\frac{\delta_{0}+1+\delta_{2}}{\delta_{2}}}\big{\\}}.$

In the $\inf\max$ above, the first term is decreasing while the second is
increasing in $\delta_{2}$. Hence, the $\inf\max$ is reached when there is
equality.

$\displaystyle\delta_{0}+1+\delta_{2}=1+\frac{\delta_{0}+1+\delta_{2}}{\delta_{2}}$
$\displaystyle\Leftrightarrow$
$\displaystyle\delta_{2}^{2}+(\delta_{0}-1)\delta_{2}-(\delta_{0}+1)=0$
$\displaystyle\Leftrightarrow$
$\displaystyle\delta_{2}=\frac{1-\delta_{0}+\sqrt{\delta_{0}^{2}+4\delta_{0}+5}}{2}$

Hence,
$\lambda^{\mathcal{I}_{3,T},\delta_{0}}=\frac{2}{3+\delta_{0}+\sqrt{\delta_{0}^{2}+4\delta_{0}+5}}$.

It follows that for $\delta^{\prime}_{0}=\frac{\delta_{0}+1}{\delta_{2}}$, we
have

$\displaystyle\lambda^{\mathcal{I}_{3,T},\delta^{\prime}_{0}}$
$\displaystyle=$
$\displaystyle\frac{2}{3+\delta^{\prime}_{0}+\sqrt{{\delta^{\prime}_{0}}^{2}+4\delta^{\prime}_{0}+5}}$
$\displaystyle<$
$\displaystyle\frac{2}{3+\delta^{\prime}_{0}+\sqrt{(\delta^{\prime}_{0}+3)^{2}}}=\frac{1}{3+\delta^{\prime}_{0}}=\lambda^{\mathcal{I}_{2,T},1+\delta^{\prime}_{0}}.$

Hence, $\lambda^{\mathcal{I}_{4,T},\delta_{0}}=\inf\limits_{\delta_{2}\geq
0}\max\big{\\{}\frac{1}{\delta_{0}+1+\delta_{2}},\frac{1}{2+\frac{\delta_{0}+1+\delta_{2}}{\delta_{2}}}\big{\\}}.$

Thus,

$\displaystyle\delta_{0}+1+\delta_{2}=2+\frac{\delta_{0}+1+\delta_{2}}{\delta_{2}}$
$\displaystyle\Leftrightarrow$
$\displaystyle\delta_{2}^{2}+(\delta_{0}-2)\delta_{2}-(\delta_{0}+1)=0$
$\displaystyle\Leftrightarrow$
$\displaystyle\delta_{2}=\frac{2-\delta_{0}+\sqrt{\delta_{0}^{2}+8}}{2}.$

Hence,
$\lambda^{\mathcal{I}_{4,T},\delta_{0}}=\frac{2}{4+\delta_{0}+\sqrt{\delta_{0}^{2}+8}}$.
∎

######  Corollary 3.

For $\frac{1}{2}\leq T<1$, we have
$\lambda^{\mathcal{I}_{3,T}}=\frac{1}{\varphi^{2}}$, where $\varphi$ is the
golden ratio, and $\lambda^{\mathcal{I}_{4,T}}=1-\frac{\sqrt{2}}{2}$.

######  Proposition 3.

For $\frac{1}{2}\leq T<1$, we have
$\gamma^{\mathcal{I}_{3,T}}=\frac{1}{\varphi^{2}}$, where $\varphi$ is the
golden ratio.

###### Proof.

For $\frac{1}{2}\leq T<1$ and $n=3$, the adversary can limit the competitive
ratio by using the following strategy:

  1. (a)

First, release a request $f_{1}=(-1,[1,3],1)$.

  2. (b)

Assuming the vehicle moves towards $f_{1}$, release
$f_{2}=(1,[2-\epsilon,4-\epsilon],\varphi)$, with
$\epsilon<\min\\{\frac{1}{3},1-T\\}$.

  3. (c)

If the vehicle keeps going towards $f_{1}$, do not release any more requests.

  4. (d)

Else, if the vehicle goes towards $f_{2}$, release
$f_{3}=(-1,[4-3\epsilon,6-3\epsilon],\varphi)$. (see Figure 2)

$t=1$-1$f_{1},f_{3}$1$f_{2}$$2-\epsilon$$4-3\epsilon$ Figure 2: vehicle’s
itinerary for $n=3$ and $\frac{1}{2}\leq T<1$ in Proposition 3.

Since $2i-1\in[t_{i},t_{i}+2]$, the offline algorithm can serve all the
requests. If the vehicle chooses to keep going towards $f_{1}$ when $f_{2}$ is
released, the competitive ratio will be $\frac{1}{1+\varphi}$. Else, if it
changes directions, the competitive ratio will be
$\frac{\varphi}{1+2\varphi}=\frac{1}{1+\varphi}=\frac{1}{\varphi^{2}}$. ∎

In Table 5, we summarise the results obtained for $n=3$.

Delay | Performance | Competitive Ratio
---|---|---
$T<1/2$ | $1/3$ | $1/3$
$1/2\leq T<1$ | $1/\varphi^{2}\approx 0.3820$ | $1/\varphi^{2}\approx 0.3820$
$1\leq T<1.5$ | $1/2$ | $1/2$
$1.5\leq T$ | 1 | 1
Table 5: Performances and Competitive Ratios for $n=3$

For $n=4$, the cases $T<\frac{1}{6}$ and $T\geq 1$ are covered by Theorem 4
and Theorem 2, respectively. In the case where $\frac{1}{2}\leq T<1$, the
performance is given in Corollary 3.

Note that for $n=4$ and $T<\frac{1}{6}$, the game can be represented as a
decision tree shown in Figure 3. Assuming $\delta_{1}=1$,
$\delta_{4}=\delta_{1}$, $\delta^{\prime}_{4}=\delta_{3}$,
$\delta^{\prime\prime}_{4}=\delta^{\prime}_{3}$ and
$\delta^{\prime\prime\prime}_{4}=\delta_{2}$, the optimal performance is

$\lambda^{\mathcal{I}_{4,T}}=\min\limits_{\delta_{2}}\max\\{\min\limits_{\delta_{3}}\max\\{\frac{\delta_{1}}{S_{4}},\frac{\delta_{3}}{S^{\prime}_{4}}\\},\min\limits_{\delta^{\prime}_{3}}\max\\{\frac{\delta^{\prime}_{3}}{S^{\prime\prime}_{4}},\frac{\delta_{2}}{S^{\prime\prime\prime}_{4}}\\}\\}.$

$f_{1}$$f_{2}$$f_{3}$$f_{4}$1$\frac{\delta_{1}}{S_{4}},\delta_{1}=\delta_{4}$toward
-1$f^{\prime}_{4}$-1$\frac{\delta_{3}}{S^{\prime}_{4}},\delta_{3}=\delta^{\prime}_{4}$toward
11toward
-1$f^{\prime}_{3}$$f^{\prime\prime}_{4}$1$\frac{\delta^{\prime}_{3}}{S^{\prime\prime}_{4}},\delta^{\prime}_{3}=\delta^{\prime\prime}_{4}$toward
-1$f^{\prime\prime\prime}_{4}$-1$\frac{\delta_{2}}{S^{\prime\prime\prime}_{4}},\delta_{2}=\delta^{\prime\prime\prime}_{4}$toward
1-1toward 11toward -1-1 Figure 3: Decision tree for the vehicle’s movements,
$T<1/6$ and at most $4$ requests. The locations of the requests are given in
the grey rectangles. The value of the competitive ratio and the condition on
the weight of the fourth request relative to each branch are indicated on the
right.

######  Proposition 4.

For $\frac{1}{3}\leq T<\frac{1}{2}$, we have
$\lambda^{\mathcal{I}_{4,T}}=2-\sqrt{3}$.

###### Proof.

For $\frac{1}{3}\leq T<\frac{1}{2}$, when the vehicle keeps moving towards
$-1$, the adversary cannot release the fourth request before $f_{1}$ is
served. This corresponds to replacing $\delta_{4}=\delta_{1}$ in the case
shown in Figure 3 with $\delta_{4}=0$. By setting
$\frac{\delta^{\prime}_{3}}{S^{\prime\prime}_{4}}=\frac{\delta_{2}}{S^{\prime\prime\prime}_{4}}$,
we obtain $\delta^{\prime}_{3}=\delta_{2}$. Setting
$\frac{\delta_{1}}{S_{4}}=\frac{\delta_{3}}{S^{\prime}_{4}}$ with
$\delta_{4}=0$ gives
$\delta_{3}=\frac{1-\delta_{2}}{2}+\frac{1}{2}\sqrt{\delta_{2}^{2}+2\delta_{2}+5}$.
Then, setting
$\frac{\delta_{1}}{S_{4}}=\frac{\delta_{2}}{S^{\prime\prime\prime}_{4}}$, we
deduce that $\delta_{2}$ is a root of $2X^{3}-3X-1$. Hence,
$\delta_{2}=\frac{1+\sqrt{3}}{2}$, and
$\lambda^{\mathcal{I}_{4,T}}=2-\sqrt{3}$.

The adversary can limit the performance to $2-\sqrt{3}$ by using the following
strategy with the optimal weights found above and $\epsilon=\frac{1}{2}-T$:

  1. (a)

First, release a request $f_{1}=(-1,[1,3],1)$.

  2. (b)

Assuming the vehicle moves towards $f_{1}$, release
$f_{2}=(1,[2-T-\epsilon,4-T-\epsilon],\delta_{2})$.

  3. (c)

If the vehicle keeps going towards $-1$, release
$f_{3}=(1,[2-\epsilon,4-\epsilon],\delta_{3})$. If the vehicle keeps going
towards $-1$, do not release a fourth request; else, if it changes directions,
release a request
$f^{\prime}_{4}=(-1,[4-3\epsilon,6-3\epsilon],\delta^{\prime}_{4})$.

  4. (d)

Else, if the vehicle changes directions, release a request
$f^{\prime}_{3}=(-1,[4-3T-3\epsilon,6-3T-3\epsilon],\delta^{\prime}_{3})$. If
it changes directions again, release a request
$f^{\prime\prime}_{4}=(1,[6-4T-5\epsilon,8-4T-5\epsilon],\delta^{\prime\prime}_{4})$;
else, release
$f^{\prime\prime\prime}_{4}=(-1,[4-2T-3\epsilon,6-2T-3\epsilon],\delta^{\prime\prime\prime}_{4})$.

This strategy satisfies the condition relative to the delays and prevents the
vehicle from serving two requests. Hence,
$\lambda^{\mathcal{I}_{4,T}}=2-\sqrt{3}$. ∎

In order to avoid a lengthy case study, the remaining competitive ratios for
$n=4$ will be listed without detailed proof; but we will give a general idea
of how they can be obtained.

######  Claim 1.

For $n=4$ and $\frac{1}{6}\leq T<1$, the competitive ratios are as follows:

  1. 1.

for $\frac{1}{6}\leq T<\frac{1}{5}$, $\gamma^{\mathcal{I}_{4,T}}\approx
0.2578$,

  2. 2.

for $\frac{1}{5}\leq T<\frac{1}{4}$,
$\gamma^{\mathcal{I}_{4,T}}=2-\sqrt{3}\approx 0.2679$,

  3. 3.

for $\frac{1}{4}\leq T<\frac{1}{3}$, $\gamma^{\mathcal{I}_{4,T}}\approx
0.2803$,

  4. 4.

for $\frac{1}{3}\leq T<\frac{1}{2}$,
$\gamma^{\mathcal{I}_{4,T}}=1-\frac{\sqrt{2}}{2}\approx 0.2929$,

  5. 5.

for $\frac{1}{2}\leq T<1$, $\gamma^{\mathcal{I}_{4,T}}\approx 0.3177$.

General Idea of the proof: If all the requests in figure 3 are maintained,
from the delay condition and from the fact that the adversary prevents the
vehicle from serving two requests, we obtain the following conditions on the
release times:

  * •

$t_{4}<\tau_{1}=2$,

  * •

$t_{3}\leq t_{4}-T<2-T$,

  * •

$t_{2}\leq t_{3}-T<2-2T$,

  * •

$t^{\prime\prime\prime}_{4}<\tau_{2}=2t_{2}<4-4T$,

  * •

$t^{\prime}_{3}<t^{\prime\prime\prime}_{4}-T<4-5T$,

  * •

$t^{\prime\prime}_{4}<\tau_{3}\leq t^{\prime}_{3}+2-T<6-6T$.

In order for the optimal offline algorithm to serve all the requests, we
require that $t^{\prime\prime}_{4}\geq 5$. Hence, this is possible only when
$T<\frac{1}{6}$.

If the adversary chooses not to release $f^{\prime\prime}_{4}$, the conditions
become:

  * •

$t_{4}<2$,

  * •

$t_{3}\leq t_{4}-T<2-T$,

  * •

$t_{2}\leq t_{3}-T<2-2T$,

  * •

$t^{\prime\prime\prime}_{4}<\tau_{2}=2t_{2}<4-4T$,

  * •

$t^{\prime}_{3}<t^{\prime\prime\prime}_{4}-T<4-5T$,

The optimal offline condition now gives $T<\frac{1}{5}$.

If the adversary chooses not to release $f_{4}$, the conditions become:

  * •

$t_{3}<\tau_{1}=2$,

  * •

$t_{2}\leq t_{3}-T<2-T$,

  * •

$t^{\prime\prime\prime}_{4}<\tau_{2}=2t_{2}<4-2T$,

  * •

$t^{\prime}_{3}<t^{\prime\prime\prime}_{4}-T<4-3T$,

  * •

$t^{\prime\prime}_{4}<\tau_{3}\leq t^{\prime}_{3}+2-T<6-4T$.

The optimal offline condition now gives $T<\frac{1}{4}$.

If the adversary chooses not to release $f_{4}$ and $f^{\prime\prime}_{4}$,
the conditions become:

  * •

$t_{3}<\tau_{1}=2$,

  * •

$t_{2}\leq t_{3}-T<2-T$,

  * •

$t^{\prime\prime\prime}_{4}<\tau_{2}=2t_{2}<4-2T$,

  * •

$t^{\prime}_{3}<t^{\prime\prime\prime}_{4}-T<4-3T$,

The optimal offline condition now gives $T<\frac{1}{3}$.

If the adversary chooses not to release $f_{4}$ and
$f^{\prime\prime\prime}_{4}$, the conditions become:

  * •

$t_{3}<\tau_{1}=2$,

  * •

$t_{2}\leq t_{3}-T<2-T$,

  * •

$t^{\prime}_{3}<\tau_{2}=2t_{2}<4-2T$,

  * •

$t^{\prime\prime}_{4}<\tau_{3}\leq t^{\prime}_{3}+2<6-2T$,

The optimal offline condition now gives $T<\frac{1}{2}$.

Solving the corresponding minmax problem in each of these cases yields the
above competitive ratios. Note that choosing not to release $f^{\prime}_{4}$
does nothing to loosen the conditions on the times. Also, choosing not to
release $f^{\prime\prime\prime}_{4}$ gives the condition $T<\frac{1}{4}$ and
yields the same competitive ratio as not releasing $f_{4}$. Finally, not
releasing $f^{\prime\prime}_{4}$ and $f^{\prime\prime\prime}_{4}$ gives
$T<\frac{1}{4}$, same as not releasing $f^{\prime\prime\prime}_{4}$, so it is
not relevant. ∎

In Table 6, we summarise the results obtained for $n=4$.

Delay | Performance | Competitive Ratio
---|---|---
$T<1/6$ | $1/4$ | $1/4$
$1/6\leq T<1/5$ | $0.2578$
$1/5\leq T<1/4$ | $2-\sqrt{3}\approx 0.2679$
$1/4\leq T<1/3$ | $0.2803$
$1/3\leq T<1/2$ | $2-\sqrt{3}\approx 0.2679$ | $1-\sqrt{2}/2\approx 0.2929$
$1/2\leq T<1$ | $1-\sqrt{2}/2\approx 0.2929$ | $0.3177$
$1\leq T<1.5$ | $1/\varphi^{2}\approx 0.3820$ | $1/\varphi^{2}\approx 0.3820$
$1.5\leq T<5/3$ | $1/2$ | $1/2$
$5/3\leq T$ | 1 | 1
Table 6: Performances and Competitive Ratios for $n=4$

We conjecture that the behaviour of the performance and competitive ratio is
the same for $n>4$ as that exhibited for $n=4$:

######  Conjecture 2.

For a fixed $n\geq 4$, the functions $\lambda^{\mathcal{I}_{n,T}}$ and
$\gamma^{\mathcal{I}_{n,T}}$ are step functions in $T$, constant on the
interval $[\frac{1}{k},\frac{1}{k-1}[$, for $2\leq k\leq 2^{n-1}-2$.

##  8 Generalisation to Geodesic Metric Spaces

In this section, we investigate which of the previous results remain valid
when the game is played on a geodesic space instead of a segment.

Recall that the _diameter_ of $E=(X,d)$ is defined as $\sup_{(x,y)\in
X^{2}}d(x,y)$.

######  Proposition 5.

Given a geodesic metric space $E$ of diameter $2$ with two points at distance
2 and given a delay $T$, the performance and competitive ratio on $E$ are at
most equal to that on $[-1,1]$. In other words, any negative result concerning
OPTiWinD on a segment can be extended to geodesic metric spaces for which the
diameter is reached.

###### Proof.

Let $E=(X,d)$ be a geodesic metric space with diameter 2 and $A,B\in X$ such
that $d(A,B)=2$. Any strategy of the adversary applicable to $[-1,1]$ can be
used on a minimum distance path $\gamma$ from $A$ to $B$. If all requests are
located on $\gamma$, since $\gamma$ is a minimum distance path, the vehicle
cannot improve its performance by moving outside of $\gamma$. Thus, for all
delay $T$, the performance and competitive ratio on $E$ are at most equal to
those on $[-1,1]$. ∎

######  Theorem 8.

Theorem 1, Theorem 3 and Theorem 4 can be extended to all geodesic metric
spaces of diameter 2.

###### Proof.

Let $E=(X,d)$ be a geodesic metric space with diameter 2. The positive part of
these results is given in Lemma 1, which states that the algorithm $GR_{0}$
guarantees a performance of $\frac{1}{n}$. This is still true when the game is
played on $E$. If the diameter of $E$ is reached, then the result follows from
Proposition 5. Otherwise, for $\epsilon>0$, we can find $A,B\in X$ such that
$d(A,B)=2-\epsilon$ and a path $\gamma$ from $A$ to $B$ of length
$2-\epsilon$. Using the same notations as in the proof of Theorem 3, we obtain
the following conditions:

  * •

$t_{n}<2-\epsilon$,

  * •

$t_{n-1}<2-\epsilon-T$,

  * •

$t_{i}<2-\epsilon-2^{n-1-i}T$,

  * •

$1+T\leq t_{2}<2-\epsilon-2^{n-3}T$.

Hence, we obtain $T<(1-\epsilon)T_{0}$. Thus, choosing
$\epsilon<1-\frac{T}{T_{0}}$ is sufficient for the strategy described in the
proof of Theorem 3 to work on $\gamma$. Theorem 1 also works on $\gamma$ as it
is a special case of Theorem 3.

In the proof of Theorem 4, all that changes when playing on $\gamma$ is the
values of the ETAs, which only affect the proof of point c). However, the
relation $\tau_{i+1}=\tau_{i}+2-2^{n-1-i}T+O(\epsilon)$ is still true. Thus,
for $\epsilon$ small enough, the optimal offline algorithm will serve all
requests, and Theorem 4 is still valid in this case. ∎

######  Definition 2.

We say that a geodesic metric space $E=(X,d)$ with origin $O$ and diameter $2$
is _centred_ if $X\subset\overline{B}(O,1)$, where $\overline{B}(O,1)$ is the
closed ball of radius $1$ centred in $O$.

######  Theorem 9.

Theorem 2 and Theorem 7 can be extended to centred geodesic metric spaces of
diameter 2.

###### Proof.

Let $E=(X,d)$ be a geodesic metric space with diameter 2 and origin $O$. In
the proof of Theorem 2, the positive part of the result is shown by
considering algorithm $GR_{1}$. When playing on $E$, we adapt $GR_{1}$ by
heading towards $O$ instead of $0$ in case (a). The proof that $GR_{1}$ work
on $E$ is identical to that of Theorem 2. The key point is that we still have
$i_{0}=\lfloor\frac{1}{2-T}\big{\rfloor}$.

In order to prove the negative result, we choose $A,B\in X$ such that
$d(A,B)=2-\epsilon^{\prime}$ and a minimum distance path $\gamma$ from $A$ to
$B$. The adversary can apply on $\gamma$ the strategy described in the proof
of Theorem 2 with one modification: for $i\geq i_{0}+2$, choose
$\eta_{i}=\frac{i-i_{0}}{n}-\frac{3}{2n}-(i-\frac{3}{2})\epsilon^{\prime}$.
This allows the relation $t_{i}=\tau_{i-1}-\frac{1}{2n}$ for $i\geq i_{0}+2$
to be valid on a path of length $2-\epsilon^{\prime}$. It follows that for
$\epsilon^{\prime}<\frac{5}{n^{2}}$, we still have $\eta_{i}<1$, $\forall
i\geq i_{0}+2$. Therefore, this strategy of the adversary limits the
competitive ratio of the vehicle to $\alpha_{n-\lfloor\frac{1}{2-T}\rfloor}$.

For Theorem 7, we choose $A$ and $B$ with $d(A,B)>2T$. In the proof of Theorem
7, $-1$ and $1$ are replaced with $A$ and $B$, respectively, and the interval
$]T-1,1-T[$ becomes $X-(\overline{B}(A,T)\cup\overline{B}(B,T))$. The rest of
the proof remains identical. ∎

######  Remark 5.

If $E$ is a circle, $E$ is not centred, and both Theorem 2 and Theorem 7 do
not apply whenever $n\geq 3$.

######  Proposition 6.

Depending on the geodesic metric space, the smallest delays for which the
optimal performance and optimal competitive ratio are greater than
$\frac{1}{n}$ may be greater than $T_{0}=\frac{1}{2^{n-3}+1}$ and
$T_{1}=\frac{1}{2^{n-1}-2}$ respectively.

###### Proof.

Let $E$ be a star with central point $O$ and $3$ branches of length $1$. Lemma
2 and Lemma 3 do not apply to $E$ as the adversary can now release requests at
the end of the third branch. It follows that Theorem 5 and Theorem 6 do no
apply when the game is played on $E$. Let $A,B$ and $C$ denote the endpoints
of the branches of the star. For $n=5$ and $T<\frac{1}{4}$, let
$\epsilon<1-4T$. The adversary will release a request $f_{1}=(A,[1,3],1)$.
Recall that when the vehicle may choose between two symmetric requests of
equal weights, it is optimal to head towards the closest one. So, while the
vehicle keeps going towards $A$, the adversary will release the following
requests: $f_{2}=(B,[2-3T-\epsilon,4-3T-\epsilon],1)$,
$f_{3}=(C,[2-2T-\epsilon,4-2T-\epsilon],1)$,
$f_{4}=(C,[2-T-\epsilon,4-T-\epsilon],1)$ and
$f_{5}=(C,[2-\epsilon,4-\epsilon],1)$. With this strategy, the adversary
limits the optimal performance to $\frac{1}{5}$, even if
$T_{0}<T<\frac{1}{4}$. Note that this strategy was not possible on the segment
because it requires that $f_{2}$ and $f_{3}$ be located in different branches
of the star, otherwise the vehicle could reach both. A similar strategy can be
used by the adversary to limit the optimal competitive ratio to $\frac{1}{5}$
when $T$ is slightly greater than $T_{1}$. ∎

##  9 Conclusion

In this paper, we introduced the delay between requests as a new parameter in
the standard online orienteering problem. While this new parameter seems very
natural, to our knowledge, it had not been studied previously. We analysed the
performances and competitive ratios in the case where the length of the time
windows is equal to the diameter of the space. We obtained a complete
resolution when the number of requests is at most 4. In the case of $n$
requests, we solved the problem when $T\geq 1$ or $T<\frac{1}{2^{n-1}-2}$. Our
results for small numbers of requests give us an accurate idea of what to
expect in the intermediate case. Other choices regarding the length of the
time windows, which may be relevant for different applications, remain to be
investigated.

## Acknowledgements

We acknowledge the support of GEO-SAFE, H2020-MSCA-RISE-2015 project # 691161.

## References

## References

  * Ausiello et al., [2004] Ausiello, G., Demange, M., Laura, L., and Paschos, V. (2004).  Algorithms for the on-line quota traveling salesman problem.  Information Processing Letters, 92(2):89 – 94.
  * Ausiello et al., [2001] Ausiello, G., Feuerstein, E., Leonardi, S., Stougie, L., and Talamo, M. (2001).  Algorithms for the on-line travelling salesman1.  Algorithmica, 29(4):560–581.
  * Awerbuch et al., [1997] Awerbuch, B., Azar, Y., Blum, A., and Vempala, S. (1997).  New approximation guarantees for minimum-weight k-trees and prize-collecting salesmen.  SIAM Journal on Computing, 28.
  * Deza and Deza, [2009] Deza, M. M. and Deza, E. (2009).  Encyclopedia of distances.  Springer, Berlin.
  * Feillet et al., [2005] Feillet, D., Dejax, P., and Gendreau, M. (2005).  Traveling salesman problems with profits.  Transportation Science, 39(2):188–205.
  * Golden et al., [1987] Golden, B. L., Levy, L., and Vohra, R. (1987).  The orienteering problem.  Naval Research Logistics (NRL), 34(3):307–318.
  * Gutiérrez et al., [2006] Gutiérrez, S., Krumke, S. O., Megow, N., and Vredeveld, T. (2006).  How to whack moles.  Theoretical Computer Science, 361(2):329–341.
  * Irani et al., [2004] Irani, S., Lu, X., and Regan, A. (2004).  On-line algorithms for the dynamic traveling repair problem.  Journal of Scheduling, 7(3):243–258.
  * Laporte and Martello, [1990] Laporte, G. and Martello, S. (1990).  The selective travelling salesman problem.  Discrete Applied Mathematics, 26(2-3):193–207.
  * Vansteenwegen et al., [2011] Vansteenwegen, P., Souffriau, W., and Oudheusden, D. V. (2011).  The orienteering problem: A survey.  European Journal of Operational Research, 209(1):1 – 10.

## Appendix

In this section, we study the sequence $(\alpha_{n})$ defined in Section 4. We
give an explicit formula for $\delta_{i}$ and calculate the limit of
$(\alpha_{n})$.

We have the following definition of $\alpha_{n}$ for $n\geq 1$:

$\alpha_{n}=\inf\limits_{\delta\in(\mathbb{R}_{+}^{*})^{n}}\max\\{\frac{\delta_{1}}{S_{2}},\cdots,\frac{\delta_{i}}{S_{i+1}},\cdots,\frac{\delta_{n-1}}{S_{n}},\frac{\delta_{n}}{S_{n}}\\},$

where $S_{i}=\sum_{k=1}^{i}\delta_{k}$. Since multiplying all the $\delta_{i}$
by a positive constant makes no difference to the ratios, we may choose
$\delta_{1}=1$. To lighten the notation, we will omit the index $n$ and will
denote $\alpha_{n}$ by $\alpha$.

######  Proposition 7.

The value of $\alpha$ is realised for a unique vector
$\delta\in(\mathbb{R}_{+}^{*})^{n}$ with $\delta_{1}=1$ such that for $1\leq
i\leq n$:

$\delta_{i}=\Big{(}\frac{1}{2}+\frac{1-2\alpha}{2\sqrt{1-4\alpha}}\Big{)}\Big{(}\frac{1+\sqrt{1-4\alpha}}{2\alpha}\Big{)}^{i-1}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ $
$\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
+\Big{(}\frac{1}{2}-\frac{1-2\alpha}{2\sqrt{1-4\alpha}}\Big{)}\Big{(}\frac{1-\sqrt{1-4\alpha}}{2\alpha}\Big{)}^{i-1}.$

###### Proof.

Note that:

$\displaystyle\inf\limits_{\delta_{n-1},\delta_{n}}\max\\{\frac{\delta_{n-2}}{S_{n-1}},\frac{\delta_{n-1}}{S_{n}},\frac{\delta_{n}}{S_{n}}\\}$
$\displaystyle=$
$\displaystyle\inf\limits_{\delta_{n-1}}\inf\limits_{\delta_{n}}\max\\{\frac{\delta_{n-2}}{S_{n-1}},\max\\{\frac{\delta_{n-1}}{S_{n}},\frac{\delta_{n}}{S_{n}}\\}\\}$
$\displaystyle=$
$\displaystyle\inf\limits_{\delta_{n-1}}\max\\{\frac{\delta_{n-2}}{S_{n-1}},\inf\limits_{\delta_{n}}\max\\{\frac{\delta_{n-1}}{S_{n}},\frac{\delta_{n}}{S_{n}}\\}\\}.$

By repeating this inversion, we obtain that:

$\displaystyle\alpha=\inf\limits_{\delta_{2}}\max\\{\frac{1}{S_{2}},\inf\limits_{\delta_{3}}\max\\{\frac{\delta_{2}}{S_{3}},\inf\limits_{\delta_{4}}\max\\{$
$\displaystyle\cdots,\inf\limits_{\delta_{n}}\max\\{\frac{\delta_{n-1}}{S_{n}},\frac{\delta_{n}}{S_{n}}\\}\cdots\\}\\}\\}$

In the above equation, the operator $\inf_{\delta_{i}}$ is applied to the
$\max$ of two terms, the first being decreasing in $\delta_{i}$ and the second
increasing in $\delta_{i}$. It follows that the optimal value is reached when:

$\forall 1\leq i\leq n-1,\leavevmode\nobreak\
\frac{\delta_{i}}{S_{i+1}}=\frac{\delta_{n}}{S_{n}}=\alpha$

Thus, we obtain the following equations $(E_{i})$, for all $2\leq i\leq n$:

$(E_{i})\leavevmode\nobreak\ \leavevmode\nobreak\
\alpha=\frac{\delta_{i}}{S_{i+1}}=\frac{\delta_{i-1}}{S_{i}}\leavevmode\nobreak\
\leavevmode\nobreak\ \mathrm{and\leavevmode\nobreak\ \leavevmode\nobreak\
}(E_{n})\leavevmode\nobreak\ \leavevmode\nobreak\
\delta_{n-1}=\delta_{n}=\alpha S_{n}.$

Thus, $\delta_{i}=\alpha S_{i+1}$ and $\delta_{i-1}=\alpha S_{i}$. Hence,
$\delta_{i}-\delta_{i-1}=\alpha\delta_{i+1}$. The sequence $(\delta_{i})$
satisfies a second order linear recurrence relation. Its characteristic
equation is $X^{2}-\frac{1}{\alpha}X+\frac{1}{\alpha}=0$ and the discriminant
is $\Delta=\frac{1}{\alpha^{2}}(1-4\alpha)$.

If $\Delta=0$, we have $\alpha=\frac{1}{4}$. Hence, $\delta_{i}=(i+1)2^{i-2}$,
for $1\leq i\leq n$. This contradicts $(E_{n})$. So $\Delta\neq 0$.

Thus the characteristic equation has two roots
$r_{\pm}=\frac{1}{2\alpha}(1\pm\sqrt{1-4\alpha})$, where $\sqrt{1-4\alpha}$
may be an imaginary number. So there exists a $\lambda$ and a $\mu$ such that
$\forall 1\leq i\leq n,\delta_{i}=\lambda r_{+}^{i-1}+\mu r_{-}^{i-1}$.

Since $\delta_{1}=1$, we have $\lambda+\mu=1$. Similarly, using $\delta_{2}$,
we obtain that
$\lambda-\mu=\frac{2}{\sqrt{\Delta}}(\delta_{2}-\frac{1}{2\alpha})$. The
result follows. ∎

######  Lemma 4.

The roots of the characteristic equation
$X^{2}-\frac{1}{\alpha}X+\frac{1}{\alpha}=0$ are complex conjugates.

###### Proof.

Using the same notations as above, let us assume that $\Delta>0$ (i.e.
$\alpha<\frac{1}{4}$). Then, $r_{+}$, $r_{-}$, $\lambda$ and $\mu$ are real
numbers. It follows from $(E_{1})$ that $\delta_{2}=\frac{1}{\alpha}-1$.
Hence, $\lambda-\mu>0$. Since $\lambda+\mu=1$, we have $\lambda>0$. Since
$\sqrt{1-4\alpha}<1$, we have $r_{+}\geq r_{-}>0$.

Since $\delta_{n-1}=\delta_{n}$, we have:

$\lambda r_{+}^{n-2}(r_{+}-1)=-\mu r_{-}^{n-2}(r_{-}-1)$ (1)

Since $\alpha<\frac{1}{4}$, we have $r_{+}\geq 2$. It follows that in Equation
1, the left hand side is positive and $\mu\neq 0$. Let us now consider two
cases:

  1. 1.

If $\mu<0$, it follows from Equation 1 that $r_{-}-1>0$, since all the other
terms are positive. Yet, $\lambda>-\mu$ and $r_{+}\geq r_{-}$. Hence, Equation
1 is impossible.

  2. 2.

If $\mu>0$, the right hand side of Equation 1 being positive requires
$r_{-}<1$. Since $r_{+}\geq 2$ and $r_{-}>0$, we have $r_{+}-1>1-r_{-}$. Yet,
since $\lambda\geq\mu$, Equation 1 is impossible.

Therefore, since $\Delta\neq 0$, we have $\Delta<0$ and $\alpha>\frac{1}{4}$.
Hence, $r_{+}$ and $r_{-}$ are complex conjugates, as are $\lambda$ and $\mu$.

∎

######  Lemma 5.

The sequence $(\alpha_{n})$ is decreasing.

###### Proof.

Choosing $(\delta_{1},\ldots,\delta_{n})$ as the vector which realises
$\alpha_{n-1}$ and $\delta_{n}=0$ yields:
$\max\\{\frac{\delta_{1}}{S_{2}},\cdots,\frac{\delta_{i}}{S_{i+1}},\cdots,\frac{\delta_{n-1}}{S_{n}},\frac{\delta_{n}}{S_{n}}\\}=\alpha_{n-1}$.
Hence, $\alpha_{n}\leq\alpha_{n-1}$. Since this is not the vector described in
Proposition 7, we have $\alpha_{n}<\alpha_{n-1}$. ∎

######  Proposition 8.

The sequence $(\alpha_{n})$ decreases towards $\frac{1}{4}$ when
$n\rightarrow+\infty$.

###### Proof.

Using the same notations as above, it follows from Proposition 7 and Lemma 4
that $\delta_{i}=2\operatorname{Re}(\lambda r_{+}^{i})>0$. Hence,
$-\frac{\pi}{2}<\arg(\lambda r_{+}^{i})<\frac{\pi}{2}$. Thus,

$i.\arg r_{+}+\arg\lambda\mod(2\pi)<\frac{\pi}{2}.$

Since $\lambda+\mu=1$, we have $\operatorname{Re}(\lambda)=\frac{1}{2}$, and
$-\frac{\pi}{2}<\arg\lambda<\frac{\pi}{2}$. Hence, $0<i.\arg
r_{+}\mod(2\pi)<\pi$. Thus, there exists an integer $k_{i}$, $0\leq k_{i}<i$,
such that $\frac{2k_{i}\pi}{i}<\arg r_{+}<\frac{(2k_{i}+1)\pi}{i}$. Since this
is true for all $1\leq i\leq n$, we have $k_{i}=0$ for all $i$, and $0<\arg
r_{+}<\frac{\pi}{n}$. Therefore $\lim_{n\rightarrow+\infty}\arg r_{+}=0$.
Since $\operatorname{Im}(r_{+})=\frac{\sqrt{4\alpha-1}}{2\alpha}$, we have
$\lim_{n\rightarrow+\infty}\alpha=\frac{1}{4}$.

∎

######  Proposition 9.

The first values of $(\alpha_{n})$ are $\alpha_{1}=1$,
$\alpha_{2}=\frac{1}{2}$, $\alpha_{3}=\frac{1}{\varphi^{2}}$, where $\varphi$
is the golden ratio, and $\alpha_{4}=\frac{1}{3}$.

###### Proof.

While $\alpha_{1}$ is trivially equal to $1$, the following terms of the
sequence are calculated using the equations $(E_{i})$.

  * •

For $n=2$, $(E_{2})$ yields $\delta_{1}=\delta_{2}=1$ and
$\alpha=\frac{1}{2}$.

  * •

For $n=3$, equations $(E_{2})$ and $(E_{3})$ yield
$\frac{1}{S_{2}}=\frac{\delta_{2}}{S_{3}}=\frac{\delta_{3}}{S_{3}}=\alpha$.
Thus, $\delta_{2}=\delta_{3}=\varphi$ and $\alpha=\frac{1}{\varphi^{2}}$.

  * •

For $n=4$, equations $(E_{2})$, $(E_{3})$ and $(E_{4})$ yield
$\frac{1}{S_{2}}=\frac{\delta_{2}}{S_{3}}=\frac{\delta_{3}}{S_{4}}=\frac{\delta_{4}}{S_{4}}=\alpha$.
Thus $\delta_{2}=2$ and $\delta_{3}=\delta_{4}=3$ and $\alpha=\frac{1}{3}$.

∎