From Chinese Postman to Salesman and Beyond I: Approximating Shortest Tours $δ$-Covering All Points on All Edges
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915168806502400 |
|---|---|
| author | Frei, Fabian Ghazy, Ahmed Hartmann, Tim A. Hörsch, Florian Marx, Dániel |
| author_facet | Frei, Fabian Ghazy, Ahmed Hartmann, Tim A. Hörsch, Florian Marx, Dániel |
| contents | 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 $δ\geq 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 $δ\geq 3/2$, the problem admits an $O(\log{n})$-approximation.
(3) If $δ$ 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 $δ$-Tour problem. In the second one we complement the approximation algorithms presented here with inapproximability results and related to parameterized complexity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_10613 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | From Chinese Postman to Salesman and Beyond I: Approximating Shortest Tours $δ$-Covering All Points on All Edges Frei, Fabian Ghazy, Ahmed Hartmann, Tim A. Hörsch, Florian Marx, Dániel Data Structures and Algorithms Computational Complexity 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 $δ\geq 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 $δ\geq 3/2$, the problem admits an $O(\log{n})$-approximation. (3) If $δ$ 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 $δ$-Tour problem. In the second one we complement the approximation algorithms presented here with inapproximability results and related to parameterized complexity. |
| title | From Chinese Postman to Salesman and Beyond I: Approximating Shortest Tours $δ$-Covering All Points on All Edges |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2410.10613 |