2024/10/14 by Frei, Fabian, Ghazy, Ahmed, Hartmann, Tim A. +2
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2410.10613
A well-studied continuous model of graphs, introduced by Dearing and Francis [Transportation Science, 1974], considers each edge as a continuous unit-length interval of points. For δ≥ 0, we introduce the problem δ-Tour, where the objective is to find the shortest tour that comes within a distance of δ of every point on every edge. It can be observed that 0-Tour is essentially equivalent to the Chinese Postman Problem, which is solvable in polynomial time. In contrast, 1/2-Tour is essentially equivalent to the Graphic Traveling Salesman Problem (TSP), which is NP-hard but admits a constant-factor approximation in polynomial time. We investigate δ-Tour for other values of δ, noting that the problem's behavior and the insights required to understand it differ significantly across various δ regimes. We design polynomial-time approximation algorithms summarized as follows: (1) For every fixed 0 < δ< 3/2, the problem δ-Tour admits a constant-factor approximation. (2) For every fixed δ≥ 3/2, the problem admits an O(logn)-approximation. (3) If δ is considered to be part of the input, then the problem admits an O(log3n)-approximation. This is the first of two articles on the δ-Tour problem. In the second one we complement the approximation algorithms presented here with inapproximability results and related to parameterized complexity.