Improved Approximation Algorithms for PRIZE-COLLECTING STEINER TREE and TSP

DOI10.1109/FOCS.2009.39MaRDI QIDQ5171192zbMATH OpenOpenAlexFDO

Authors Aaron Archer, MohammadHossein Bateni, Mohammad T. Hajiaghayi, Howard Karloff

Publication date 25 July 2014

Published in 2009 50th Annual IEEE Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/focs.2009.39

Mathematics Subject Classification ID

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

Cited in

(6)

• A primal-dual approximation algorithm for the asymmetric prize-collecting TSP
• Euclidean prize-collecting Steiner forest
• From cost sharing mechanisms to online selection problems
• On the approximability of dense Steiner problems
• A 2-approximation for the \(k\)-prize-collecting Steiner tree problem
• Improved approximation algorithm for the asymmetric prize-collecting TSP

This page was built for publication: Improved Approximation Algorithms for PRIZE-COLLECTING STEINER TREE and TSP

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