Bicriteria Network Design via Iterative Rounding

摘要：

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.

作者: Piotr Krysta

作者单位: Department of Computer Science, Dortmund University Baroper Str. 301, 44221 Dortmund, Germany

会议类型: 国际会议

会议名称: The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)

会议地点: 昆明

会议语种:英文

页码: 179-187

在线出版日期: 2005-08-01（万方平台首次上网日期，不代表论文的发表时间）