From Chinese Postman to Salesman and Beyond I: Approximating Shortest Tours $\delta$-Covering All Points on All Edges

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 $\delta \geq 0$, we introduce the problem $\delta$-Tour, where the objective is to find the shortest tour that comes within a distance of $\delta$ 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 $\delta$-Tour for other values of $\delta$, noting that the problem's behavior and the insights required to understand it differ significantly across various $\delta$ regimes. We design polynomial-time approximation algorithms summarized as follows: (1) For every fixed $0<\delta<3/2$, the problem $\delta$-Tour admits a constant-factor approximation. (2) For every fixed $\delta \geq 3/2$, the problem admits an $O(\log{n})$-approximation. (3) If $\delta$ is considered to be part of the input, then the problem admits an $O(\log^3{n})$-approximation. This is the first of two articles on the $\delta$-Tour problem. In the second one we complement the approximation algorithms presented here with inapproximability results and related to parameterized complexity.

• Publication year

  2024

• Venue

  Unknown venue

• Publication date

  2024-10-14

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 2410.10613
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• From Chinese Postman to Salesman and Beyond: Shortest Tour δ-Covering All Points on All Edges

  2024cited by this paper
• Approximating δ-Covering

  2024cited by this paper
• Dispersing Obnoxious Facilities on Graphs by Rounding Distances

  2022cited by this paper
• Continuous facility location on graphs

  2020cited by this paper
• Dispersing Obnoxious Facilities on a Graph

  2018cited by this paper
• Hardness Results and Approximation Algorithms for the Minimum Dominating Tree Problem

  2018cited by this paper
• Graph Theory

  2016cited by this paper
• Shorter tours by nicer ears: 7/5-approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs

  2012cited by this paper
• Combinatorial optimization. Polyhedra and efficiency.

  2003cited by this paper
• Improved Approximations for Tour and Tree Covers

  2000influential reference
• Approximating the Tree and Tour Covers of a Graph

  1993cited by this paper
• Obnoxious Facility Location on Graphs

  1991cited by this paper
• New Results on the Complexity of p-Center Problems

  1983cited by this paper
• An O ((nlog p)2) Algorithm for the Continuous p-Center Problem on a Tree

  1980cited by this paper
• An Algorithmic Approach to Network Location Problems. I: The p-Centers

  1979cited by this paper
• A Min-Max Theorem for p-Center Problems on a Tree

  1977cited by this paper
• Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem

  1976cited by this paper
• Vertex packings: Structural properties and algorithms

  1975influential reference
• A Minimax Location Problem on a Network

  1974cited by this paper
• Matching, Euler tours and the Chinese postman

  1973cited by this paper
• Approximation algorithms for combinatorial problems

  1973cited by this paper

• No citing papers are available for this paper.