TY - GEN
T1 - A dual-fitting 3/2-approximation algorithm for some minimum-cost graph problems
AU - Davis, James M.
AU - Williamson, David P.
PY - 2012
Y1 - 2012
N2 - In an ESA 2011 paper, Couëtoux [2] gives a beautiful 3/2-approximation algorithm for the problem of finding a minimum-cost set of edges such that each connected component has at least k vertices in it. The algorithm improved on previous 2-approximation algorithms for the problem. In this paper, we reanalyze Couëtoux's algorithm using dual-fitting and show how to generalize the algorithm to a broader class of graph problems previously considered in the literature.
AB - In an ESA 2011 paper, Couëtoux [2] gives a beautiful 3/2-approximation algorithm for the problem of finding a minimum-cost set of edges such that each connected component has at least k vertices in it. The algorithm improved on previous 2-approximation algorithms for the problem. In this paper, we reanalyze Couëtoux's algorithm using dual-fitting and show how to generalize the algorithm to a broader class of graph problems previously considered in the literature.
UR - https://www.scopus.com/pages/publications/84866644289
UR - https://www.scopus.com/pages/publications/84866644289#tab=citedBy
U2 - 10.1007/978-3-642-33090-2_33
DO - 10.1007/978-3-642-33090-2_33
M3 - Conference contribution
AN - SCOPUS:84866644289
SN - 9783642330896
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 373
EP - 382
BT - Algorithms, ESA 2012 - 20th Annual European Symposium, Proceedings
T2 - 20th Annual European Symposium on Algorithms, ESA 2012
Y2 - 10 September 2012 through 12 September 2012
ER -