A constant-factor approximation algorithm for TSP with pairwise-disjoint connected neighborhoods in the plane

DOI10.1145/1810959.1810992zbMath1284.68673OpenAlexW2079896400MaRDI QIDQ5405881

Joseph S. B. Mitchell

Publication date: 3 April 2014

Published in: Proceedings of the twenty-sixth annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1810959.1810992

zbMATH Keywords

TSPapproximation algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (7)

A joint optimization of data ferry trajectories and communication powers of ground sensors for long-term environmental monitoring ⋮ Stochastic runtime analysis of a cross-entropy algorithm for traveling salesman problems ⋮ Constant-Factor Approximation for TSP with Disks ⋮ Unnamed Item ⋮ The Shortest Separating Cycle Problem ⋮ A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics ⋮ On the total perimeter of homothetic convex bodies in a convex container

This page was built for publication: A constant-factor approximation algorithm for TSP with pairwise-disjoint connected neighborhoods in the plane