Constant-factor approximation for TSP with disks

DOI10.1007/978-3-319-44479-6_15MaRDI QIDQ4604382zbMATH OpenOpenAlexFDO

Authors Adrian Dumitrescu, Csaba D. Tóth

Publication date 26 February 2018

Published in A Journey Through Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1506.07903

zbMATH Keywords

\(O(1)\)-approximationconstant-ratio approximationminimum weight hitting set problem

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Abstract: We revisit the traveling salesman problem with neighborhoods (TSPN) and present the first constant-ratio approximation for disks in the plane: Given a set of $n$ disks in the plane, a TSP tour whose length is at most $O(1)$ times the optimal can be computed in time that is polynomial in $n$. Our result is the first constant-ratio approximation for a class of planar convex bodies of arbitrary size and arbitrary intersections. In order to achieve a $O(1)$-approximation, we reduce the traveling salesman problem with disks, up to constant factors, to a minimum weight hitting set problem in a geometric hypergraph. The connection between TSPN and hitting sets in geometric hypergraphs, established here, is likely to have future applications.

Recommendations

• Approximation algorithms for TSP with neighborhoods in the plane
• Approximation algorithms for TSP with neighborhoods in the plane
• A constant-factor approximation algorithm for TSP with pairwise-disjoint connected neighborhoods in the plane
• TSP with neighborhoods of varying size
• scientific article; zbMATH DE number 1947392

Cites work

• scientific article; zbMATH DE number 3883609 (Why is no real title available?)
• scientific article; zbMATH DE number 3588048 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1017008 (Why is no real title available?)
• scientific article; zbMATH DE number 1182917 (Why is no real title available?)
• scientific article; zbMATH DE number 1775442 (Why is no real title available?)
• scientific article; zbMATH DE number 1424303 (Why is no real title available?)
• scientific article; zbMATH DE number 1436138 (Why is no real title available?)
• A PTAS for TSP with neighborhoods among fat regions in the plane
• A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics
• A constant-factor approximation algorithm for TSP with pairwise-disjoint connected neighborhoods in the plane
• A subexponential bound for linear programming
• APPROXIMATION ALGORITHMS FOR THE EUCLIDEAN TRAVELING SALESMAN PROBLEM WITH DISCRETE AND CONTINUOUS NEIGHBORHOODS
• Almost optimal set covers in finite VC-dimension
• Approximation algorithms for TSP with neighborhoods in the plane
• Approximation algorithms for TSP with neighborhoods in the plane
• Approximation algorithms for the Geometric Covering Salesman Problem
• Combinatorial Optimization with Explicit Delineation of the Ground Set by a Collection of Subsets
• Computational geometry. Algorithms and applications.
• Epsilon nets and union complexity
• Euclidean Traveling Salesman Tours through Stochastic Neighborhoods
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• Hitting sets when the VC-dimension is small
• Improved approximation algorithms for geometric set cover
• Improved local search for geometric hitting set
• Improved results on geometric hitting set problems
• Near-linear approximation algorithms for geometric hitting sets
• On the complexity of approximating TSP with neighborhoods and related problems
• On the minimum corridor connection problem and other generalized geometric problems
• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Reducing curse of dimensionality: improved PTAS for TSP (with neighborhoods) in doubling metrics
• TSP with neighborhoods of varying size
• The Euclidean traveling salesman problem is NP-complete
• The traveling salesman problem for lines, balls, and planes
• The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme
• Violator spaces: Structure and algorithms
• Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling

Cited in

(3)

• A constant-factor approximation algorithm for TSP with pairwise-disjoint connected neighborhoods in the plane
• The traveling salesman problem for lines, balls and planes
• A constant-factor approximation for multi-covering with disks

This page was built for publication: Constant-factor approximation for TSP with disks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4604382)