Constant-Factor Approximation for TSP with Disks
From MaRDI portal
Publication:4604382
DOI10.1007/978-3-319-44479-6_15zbMath1394.90479arXiv1506.07903OpenAlexW2228088547MaRDI 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
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)
Cites Work
- 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
- 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
