I have been working on a project that turns out to be a special case of the directed version of the survivable network problem.

Iterative rounding gives a 2-approximation of the undirected case. I'm wondering if the directed case has been studied at all and if so, what approximations can be guaranteed.

  • 3
    $\begingroup$ It would be helpful if you described what the survivable network problem is. $\endgroup$
    – Lev Reyzin
    Commented Aug 13, 2015 at 21:27

1 Answer 1


The directed versions are much harder. A survey by Nutov available on his web page is a good starting point. http://www.openu.ac.il/home/nutov/Survivable-Network.pdf


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.