Approximating min-cost chain-constrained spanning trees: a reduction from weighted to unweighted problems

• 成果类型: Article
• 署名作者: Linhares, Andre; Swamy, Chaitanya
• 署名单位: University of Waterloo
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-017-1150-7
• 发表日期: 2018
• 页码: 17-34
• 关键词: network-design; algorithms

摘要

We study the min-cost chain-constrained spanning-tree (MCCST) problem: find a min-cost spanning tree in a graph subject to degree constraints on a nested family of node sets. We devise the first polytime algorithm that finds a spanning tree that (i) violates the degree constraints by at most a constant factor and (ii) whose cost is within a constant factor of the optimum. Previously, only an algorithm for unweighted CCST was known (Olver and Zenklusen in Proceedings of the 16th IPCO, pp 324-335, 2013), which satisfied (i) but did not yield any cost bounds. This also yields the first result that obtains an O(1)-factor for both the cost approximation and violation of degree constraints for any spanning-tree problem with general degree bounds on node sets, where an edge participates in a super-constant number of degree constraints. A notable feature of our algorithm is that we reduce MCCST to unweighted CCST (and then utilize Olver and Zenklusen in Proceedings of the 16th IPCO, pp 324-335, 2013) via a novel application of Lagrangian duality to simplify the cost structure of the underlying problem and obtain a decomposition into certain uniform-cost subproblems. We show that this Lagrangian-relaxation based idea is in fact applicable more generally and, for any cost-minimization problem with packing side-constraints, yields a reduction from the weighted to the unweighted problem. We believe that this reduction is of independent interest. As another application of our technique, we consider the k-budgeted matroid basis problem, where we build upon a recent rounding algorithm of Bansal and Nagarajan (Proceedings of IPCO 2016. arXiv: 1512.02254, 2015) to obtain an improved nO(k1.5/ )- time algorithm that returns a solution that satisfies (any) one of the budget constraints exactly and incurs a (1 + )- violation of the other budget constraints.