A PTAS for TSP with neighborhoods among fat regions in the plane

zbMATH Open1302.68322arXiv1703.01646MaRDI QIDQ2934576FDOQ2934576

Authors: Joseph S. B. Mitchell 

Publication date: 18 December 2014

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

Recommendations

• Approximation algorithms for TSP with neighborhoods in the plane
• Approximation algorithms for TSP with neighborhoods in the plane
• TSP with neighborhoods of varying size

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Cited In (24)

• The shortest separating cycle problem
• Reducing curse of dimensionality: improved PTAS for TSP (with neighborhoods) in doubling metrics
• Reducing curse of dimensionality: improved PTAS for TSP (with neighborhoods) in doubling metrics
• A joint optimization of data ferry trajectories and communication powers of ground sensors for long-term environmental monitoring
• Algorithms for interval structures with applications
• Cooperative TSP
• Title not available (Why is that?)
• Minimum covering with travel cost
• APPROXIMATION ALGORITHMS FOR THE EUCLIDEAN TRAVELING SALESMAN PROBLEM WITH DISCRETE AND CONTINUOUS NEIGHBORHOODS
• Constant-factor approximation for TSP with disks
• New approximation algorithms for touring regions
• Automata, Languages and Programming
• On the minimum corridor connection problem and other generalized geometric problems
• Complexity and approximability of the Euclidean generalized traveling salesman problem in grid clusters
• On Approximating the TSP with Intersecting Neighborhoods
• The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme
• Approximation algorithms for TSP with neighborhoods in the plane
• Computing shortest heterochromatic monotone routes
• Approximation schemes for the generalized traveling salesman problem
• A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics
• A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics
• Controlled mobility in stochastic and dynamic wireless networks
• Title not available (Why is that?)
• Algorithms for interval structures with applications

This page was built for publication: A PTAS for TSP with neighborhoods among fat regions in the plane

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