2010/04/08 by Paulo Feofiloff, Cristina G. Fernandes, Feofiloff, Paulo +5
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1004.1437
openalex publication_date 2010/04/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The primal-dual scheme has been used to provide approximation algorithms for many problems. Goemans and Williamson gave a (2-1/(n-1))-approximation for the Prize-Collecting Steiner Tree Problem that runs in O(n3 log n) time. it applies the primal-dual scheme once for each of the n vertices of the graph. Johnson, Minkoff and Phillips proposed a faster implementation of Goemans and Williamson's algorithm. We give a proof that the approximation ratio of this implementation is exactly 2.