Constant-Factor Approximation for TSP with Disks

DOI10.1007/978-3-319-44479-6_15zbMath1394.90479arXiv1506.07903MaRDI QIDQ4604382

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

minimum weight hitting set problem; \(O(1)\)-approximation; constant-ratio approximation

Mathematics Subject Classification ID

90C59: Approximation methods and heuristics in mathematical programming

90C27: Combinatorial optimization

Cites Work

• Improved results on geometric hitting set problems
• A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics
• On the total perimeter of homothetic convex bodies in a convex container
• On the minimum corridor connection problem and other generalized geometric problems
• On the complexity of approximating TSP with neighborhoods and related problems
• Improved approximation algorithms for geometric set cover
• Violator spaces: Structure and algorithms
• Hitting sets when the VC-dimension is small
• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
• The Euclidean traveling salesman problem is NP-complete
• Approximation algorithms for the Geometric Covering Salesman Problem
• Almost optimal set covers in finite VC-dimension
• A subexponential bound for linear programming
• Near-linear approximation algorithms for geometric hitting sets
• The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme
• Euclidean Traveling Salesman Tours through Stochastic Neighborhoods
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• 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
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• Approximation algorithms for TSP with neighborhoods in the plane
• Reducing Curse of Dimensionality: Improved PTAS for TSP (with Neighborhoods) in Doubling Metrics
• The Traveling Salesman Problem for Lines, Balls, and Planes
• Epsilon nets and union complexity
• A constant-factor approximation algorithm for TSP with pairwise-disjoint connected neighborhoods in the plane
• TSP with neighborhoods of varying size
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item