Constant-factor approximation for TSP with disks

DOI10.1007/978-3-319-44479-6_15zbMATH Open1394.90479arXiv1506.07903OpenAlexW2228088547MaRDI QIDQ4604382FDOQ4604382

Authors: Adrian Dumitrescu, Csaba D. Tóth 

Publication date: 26 February 2018

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

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.

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

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

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)

Cites Work

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

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)