We study the min-cost chain-constrained spanning-tree (abbreviated 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 (ⅰ) violates the degree constraints by at most a constant factor and (ⅱ) whose cost is within a constant factor of the optimum. Previously, only an algorithm for unweighted CCST was known [13], which satisfied (ⅰ) 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 multiple degree constraints. A notable feature of our algorithm is that we reduce MCCST to unweighted CCST (and then utilize [13]) 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 [4] to obtain an improved n~O(k~(1.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.
展开▼
