A Unified PTAS for Prize Collecting TSP and Steiner Tree Problem in Doubling Metrics

DOI10.1145/3378571zbMath1484.68331OpenAlexW3011328295MaRDI QIDQ4987441

T.-H. Hubert Chan, Haotian Jiang, Shaofeng H.-C. Jiang

Publication date: 3 May 2021

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/9478/

zbMATH Keywords

Steiner tree problemdoubling dimensionpolynomial-time approximation schemeprize-collecting traveling salesman problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (1)

Formulations and a Lagrangian relaxation approach for the prize collecting traveling salesman problem

This page was built for publication: A Unified PTAS for Prize Collecting TSP and Steiner Tree Problem in Doubling Metrics