Approximate k-MSTs and k-Steiner trees via the primal-dual method and Lagrangean relaxation

• 成果类型: Article
• 署名作者: Chudak, FA; Roughgarden, T; Williamson, DP
• 署名单位: Swiss Federal Institutes of Technology Domain; ETH Zurich; University of California System; University of California Berkeley; International Business Machines (IBM); IBM USA
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-003-0479-2
• 发表日期: 2004
• 页码: 411-421
• 关键词: algorithm

摘要

Garg [10] gives two approximation algorithms for the minimum-cost tree spanning k vertices in an undirected graph. Recently Jain and Vazirani [15] discovered primal-dual approximation algorithms for the metric uncapacitated facility location and k-median problems. In this paper we show how Garg's algorithms can be explained simply with ideas introduced by Jain and Vazirani, in particular via a Lagrangean relaxation technique together with the primal-dual method for approximation algorithms. We also derive a constant factor approximation algorithm for the k-Steiner tree problem using these ideas, and point out the common features of these problems that allow them to be solved with similar techniques.