A constant-factor approximation algorithm for TSP with pairwise-disjoint connected neighborhoods in the plane
From MaRDI portal
Publication:5405881
DOI10.1145/1810959.1810992zbMath1284.68673OpenAlexW2079896400MaRDI QIDQ5405881
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
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
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
