Approximation Algorithms for Orienteering with Time Windows

الأصل · EN

Orienteering is the following optimization problem: given an edge-weighted graph (directed or undirected), two nodes s,t and a time limit T, find an s-t walk of total length at most T that maximizes the number of distinct nodes visited by the walk. One obtains a generalization, namely orienteering with time-windows (also referred to as TSP with time-windows), if each node v has a specified time-window [R(v), D(v)] and a node v is counted as visited by the walk only if v is visited during its time-window. For the time-window problem, an O() approximation can be achieved even for directed graphs if the algorithm is allowed quasi-polynomial time. However, the best known polynomial time approximation ratios are O(²) for undirected graphs and O(⁴) in directed graphs. In this paper we make some progress towards closing this discrepancy, and in the process obtain improved approximation ratios in several natural settings. Let L(v) = D(v) - R(v) denote the length of the time-window for v and let = ᵥ L(v) and = ᵥ L(v). Our results are given below with αdenoting the known approximation ratio for orienteering (without time-windows). Currently α= (2+) for undirected graphs and α= O(²) in directed graphs. 1. An O(α) approximation when R(v) and D(v) are integer valued for each v. 2. An O(α, /) approximation. 3. An O(α /) approximation when no start and end points are specified. In particular, if / is poly-bounded, we obtain an O(n) approximation for the time-window problem in undirected graphs.