Uniform framework for approximating weighted connectivity problems

Samir Khuller*, Balaji Raghavachari, An Zhu

*Corresponding author for this work

Research output: Contribution to conferencePaperpeer-review

15 Scopus citations

Abstract

We introduce a new algorithmic technique that applies to several graph connectivity problems. Its power is demonstrated by experimental studies of the minimum-weight strongly-connected spanning subgraph problem and the minimum-weight augmentation problem. Even though we are unable to improve the approximation ratios for these problems, our studies indicate that the new method generates significantly better solutions than the current known approximation algorithms, and yields solutions very close to optimal. We believe that our technique will eventually lead to algorithms that improve the performance ratios as well.

Original languageEnglish (US)
StatePublished - Jan 1 1999
EventProceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms - Baltimore, MD, USA
Duration: Jan 17 1999Jan 19 1999

Other

OtherProceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms
CityBaltimore, MD, USA
Period1/17/991/19/99

ASJC Scopus subject areas

  • Chemical Health and Safety
  • Software
  • Safety, Risk, Reliability and Quality
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Uniform framework for approximating weighted connectivity problems'. Together they form a unique fingerprint.

Cite this