We study the Deadline TSP problem. The input consists of a complete undirected graph G = (V, E), a metric c : E → Z_+, a reward function w : V → Z_+, a non-negative deadline function d : V → Z_+, and a starting node s ∈ V. A feasible solution is a path starting at s. Given such a path and a node v ∈ V, we say that the path visits v by its deadline if the length of the prefix of the path starting at s until the first time it traverses v is at most d(v) (in particular, it means that the path traverses v). If a path visits v by its deadline, it gains the reward w(v). The objective is to find a path P starting at s that maximizes the total reward. In our work we present a bi-criteria (1 + ε, α/1+ε)-approximation algorithm for every ε > 0 for the Deadline TSP, where a is the approximation ratio for Deadline TSP with a constant number of deadlines (currently α = 1/3 by [5]) and thus significantly improving the previously best known bi-criteria approximation for that problem (a bi-criteria (1 + ε, 1/O(log(1/ε)))-approximation algorithm for every ε > 0 by Bansal et al. [1]). We also present improved bi-criteria (1 + ε, 1/1+ε)-approximation algorithms for the Deadline TSP on weighted trees.
展开▼
