5
$\begingroup$

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.

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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