  We develop fast approximation algorithms for the minimum-cost version of the
Bounded-Degree MST problem (BD-MST) and its generalization the Crossing
Spanning Tree problem (Crossing-ST). We solve the underlying LP to within a
$(1+\epsilon)$ approximation factor in near-linear time via the multiplicative
weight update (MWU) technique. This yields, in particular, a near-linear time
algorithm that outputs an estimate $B$ such that $B \le B^* \le \lceil
(1+\epsilon)B \rceil +1$ where $B^*$ is the minimum-degree of a spanning tree
of a given graph. To round the fractional solution, in our main technical
contribution, we describe a fast near-linear time implementation of
swap-rounding in the spanning tree polytope of a graph. The fractional solution
can also be used to sparsify the input graph that can in turn be used to speed
up existing combinatorial algorithms. Together, these ideas lead to
significantly faster approximation algorithms than known before for the two
problems of interest. In addition, a fast algorithm for swap rounding in the
graphic matroid is a generic tool that has other applications, including to TSP
and submodular function maximization.
