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 - http://www.scopus.com/inward/record.url?scp=84866644289&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84866644289&partnerID=8YFLogxK

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 -