We study the {em min-cost chain-constrained spanning-tree} (abbreviated mcst) problem: find a min-cost spanning tree in a graph subject to degree constraints on a nested family of node sets. We devise the {em first} polytime algorithm that finds a spanning tree that (i) violates the degree constraints by at most a constant factor {em and} (ii) whose cost is within a constant factor of the optimum. Previously, only an algorithm for {em unweighted} cst was known cite{olver}, which satisfied (i) but did not yield any cost bounds. This also yields the first result that obtains an $O(1)$-factor for {em 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 {em reduce} mcst to unweighted cst (and then utilize cite{olver}) via a novel application of {em Lagrangian duality} to simplify the {em 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 {em $k$-budgeted matroid basis} problem, where we build upon a recent rounding algorithm of cite{BansalN16} to obtain an improved $n^{O(k^{1.5}/epsilon)}$-time algorithm that returns a solution that satisfies (any) one of the budget constraints exactly and incurs a $(1+epsilon)$-violation of the other budget constraints.
Download