  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.
