On Approximating A Geometric Prize-Collecting Traveling Salesman Problem With Time Windows

example, consider a repairman that is supposed to visit customers at
their homes. Each customer is given a time window during which the
repairman is allowed to arrive. The goal is to find a schedule that
visits as many homes as possible. We refer to this problem as the
Prize-Collecting Traveling Salesman Problem with time windows (PC-TW-TSP).

We consider two versions of PC-TW-TSP. In the first version, jobs are
located on a line, have release times and deadlines but no processing
times. A geometric interpretation of the problem is used that
generalizes the Erd\H os-Szekeres Theorem. We present an $O(\log n)$
approximation algorithm for this case, where $n$ denotes the number of
jobs. This algorithm can be extended to deal with non-unit job
profits.

The second version deals with a general case of asymmetric distances
between locations. We define a density parameter that, loosely
speaking, bounds the number of zig-zags between locations within a
time window. We present a dynamic programming algorithm that finds a
tour that visits at least $OPT/\text{\emph{density}}$ locations during
their time windows. This algorithm can be extended to deal with
non-unit job profits and processing times.

Joint work with Reuven Bar-Yehuda and Shimon (Moni) Shahar.
This paper will be presented in ESA-03.