Improved Approximation Algorithms for PRIZE-COLLECTING STEINER TREE and TSP

DOI10.1109/FOCS.2009.39zbMath1292.68161OpenAlexW2114997377MaRDI QIDQ5171192

Aaron Archer, MohammadHossein Bateni, Howard J. Karloff, Mohammad Taghi Hajiaghayi

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

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

Related Items (5)

From Cost Sharing Mechanisms to Online Selection Problems ⋮ On the approximability of dense Steiner problems ⋮ Improved approximation algorithm for the asymmetric prize-collecting TSP ⋮ A primal-dual approximation algorithm for the asymmetric prize-collecting TSP ⋮ Euclidean prize-collecting Steiner forest

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