A dual-fitting 3/2-approximation algorithm for some minimum-cost graph problems

James M. Davis, David P. Williamson

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationAlgorithms, ESA 2012 - 20th Annual European Symposium, Proceedings
Pages373-382
Number of pages10
DOIs
StatePublished - 2012
Event20th Annual European Symposium on Algorithms, ESA 2012 - Ljubljana, Slovenia
Duration: Sep 10 2012Sep 12 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7501 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other20th Annual European Symposium on Algorithms, ESA 2012
Country/TerritorySlovenia
CityLjubljana
Period9/10/129/12/12

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'A dual-fitting 3/2-approximation algorithm for some minimum-cost graph problems'. Together they form a unique fingerprint.

Cite this