Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Networks

Bicriteria Network Design via Iterative Rounding

Piotr KrystaContact Information

(1)  Department of Computer Science, Dortmund University, Baroper Str. 301, 44221 Dortmund, Germany
Abstract
We study the edge-connectivity survivable network design problem with an additional linear budget constraint. We give a strongly polynomial time (3, 3)-approximation algorithm for this problem, by extending a linear programming based technique of iterative rounding. Previously, a (4, 4)-approximation algorithm for this problem was known. The running time of this previous algorithm is not strongly polynomial.

Contact Information Piotr Krysta
Email: piotr.krysta@cs.uni-dortmund.de
Fulltext Preview (Small, Large)
Image of the first page of the fulltext


Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.110 • Server: mpweb05
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)