Reducing curse of dimensionality: improved PTAS for TSP (with neighborhoods) in doubling metrics

DOI10.1137/1.9781611974331.CH54zbMATH Open1411.68183OpenAlexW4248384829MaRDI QIDQ4575633FDOQ4575633

Authors:

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611974331.ch54

Recommendations

• Reducing curse of dimensionality: improved PTAS for TSP (with neighborhoods) in doubling metrics
• A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics
• A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics
• A PTAS for TSP with neighborhoods among fat regions in the plane
• Maximum Scatter TSP in Doubling Metrics

Mathematics Subject Classification ID

Randomized algorithms (68W20) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cited In (8)

• The shortest separating cycle problem
• Reducing curse of dimensionality: improved PTAS for TSP (with neighborhoods) in doubling metrics
• A PTAS for the Steiner forest problem in doubling metrics
• Constant-factor approximation for TSP with disks
• Approximating TSP on metrics with bounded global growth
• A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics
• A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics
• A unified PTAS for prize collecting TSP and Steiner tree problem in doubling metrics

This page was built for publication: Reducing curse of dimensionality: improved PTAS for TSP (with neighborhoods) in doubling metrics

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