A uniform framework for approximating weighted connectivity problems
Samir Khuller, Balaji Raghavachari, An Zhu · 1999
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. 1 Introduction Let a weighted graph G = (V; E) represent all the feasible links of a potential communications network. A minimum spanning tree in G is the cheapest connected subgraph, i.e., the cheapest network that will allow the sites to communicate. Such a network is highly susceptible to failures, since it cannot even survive a single link or site failure. For more rel...