Allan Borodin, Jon Kleinberg, et al.
Journal of the ACM
Paper
An iterative rounding 2-approximation algorithm for the element connectivity problem
Abstract
An iterative rounding 2-approximation algorithm for the element connectivity problem was studied. The set of vertices was partitioned into terminals and nonterminals in the element connectivity problem. The variants of survivable network design problem (SNDP) are all known to be NP-hard. It was observed that the best approximation algorithm for the EC-SNDP showed performance guarantee of 2 and iteratively rounds solutions to a linear programming relaxation of the problem.
Related
Conference paper
Faster approximation algorithms for the minimum latency problem
Aaron Archer, David P. Williamson
SODA 1998
David P. Williamson, Michel X. Goemans
INFORMS Journal on Computing
Fabián A. Chudak, Michel X. Goemans, et al.
Operations Research Letters