A unified algorithm for degree bounded survivable network design

• 成果类型: Article
• 署名作者: Lau, Lap Chi; Zhou, Hong
• 署名单位: Chinese University of Hong Kong
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-015-0858-5
• 发表日期: 2015
• 页码: 515-532
• 关键词: Approximation; constraints

摘要

We present an approximation algorithm for the minimum bounded degree Steiner network problem that returns a Steiner network of cost at most two times the optimal and the degree on each vertex is at most , where is the maximum connectivity requirement and is the given degree bound on . This unifies, simplifies, and improves the previous results for this problem.