Conference paper
Adversarial queueing theory
Allan Borodin, Jon Kleinberg, et al.
STOC 1996
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.
Allan Borodin, Jon Kleinberg, et al.
STOC 1996
Lisa Fleischer, Kamal Jain, et al.
Journal of Computer and System Sciences
Lisa Fleischer, Michel X. Goemans, et al.
SODA 2006
Kirsten Hildrum, Fred Douglis, et al.
IPDPS 2007