# Approximation Algorithms for Time-Window TSP

and Prize Collecting TSP Problems

## Su Jia, Stony Brook University

## February 14, 2017

We give new approximation algorithms for robot routing
problems that are variants of the classical traveling salesperson
problem (TSP). We are to find a path for a robot, moving at speed at
most $s$, to visit a set $V=\{v_1,\ldots,v_n\}$ of sites, each having
an associated time window of availability, $[r_i,d_i]$, between a
release time $r_i$ and a deadline $d_i$.

In the *time-window prize collecting problem (TWPC)*, the
objective is to maximize the number of sites visited within their time
windows.

In the *time-window TSP problem (TWTSP)*, the objective is to
minimize the length of a path that visits *all* of the sites $V$
within their respective time windows, if it is possible to do so
within the speed bound $s$.

For sites on a line, we give approximation algorithms for TWPC and
TWTSP that produce paths that visit sites $v_i$ at times within the
relaxed time windows $[r_i-\varepsilon L_i,d_i+\varepsilon L_i]$, for fixed
$\varepsilon>0$, where $L_i=d_i-r_i$; the running time is
$O((nL_{max})^{O(\frac{\log L_{max}} {\log (1+\varepsilon)})})$,
where $L_{max}=\max_i L_i$.

For TWPC, the computed path visits at least $k^*$ (the cardinality of
an optimal solution to TWPC) sites; for TWTSP, the computed path is of
length at most $\lambda^*$ (the length of an optimal TWTSP solution).

For general instances of sites in a metric space, we give
approximation algorithms that apply to instances with certain special
structure of the time windows (that they are ``dyadic'' or that they
are ``elementary''), giving paths whose lengths are within a bounded
factor of the optimal length, $\lambda^*(s)$, for the given speed $s$,
while relaxing the speed to be a factor greater than $s$; for
arbitrary time windows, we give an $O(\log n)$-approximation for
TWTSP, assuming unbounded speed ($s=\infty$).