Approximation algorithms for the k-edge-connectivity augmentation problem
Toshiya Mashima, Takahiro Watanabe · 2002
Reposing and evaluating approximation algorithms for the weighted k-edge-connectivity augmentation problem are the subjects of the paper. First, a new approximation algorithm MW is proposed, and it is proved that its worst approximation is bounded by twice the optimum if the edge connectivity is increased by one. Secondly it is experimentally shown that FSM based on maximum-cost matchings produces the best approximation among the five approximation algorithms: MW and the four previously proposed ones.