TY - GEN

T1 - Fast approximation algorithms for bounded degree and crossing spanning tree problems

AU - Chekuri, Chandra

AU - Quanrud, Kent

AU - Torres, Manuel R.

N1 - Publisher Copyright:
© Chandra Chekuri, Kent Quanrud, and Manuel R. Torres; licensed under Creative Commons License CC-BY 4.0

PY - 2021/9/1

Y1 - 2021/9/1

N2 - 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 + ϵ) 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 ≤ B∗ ≤ ⌈(1 + ϵ)B⌉ + 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.

AB - 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 + ϵ) 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 ≤ B∗ ≤ ⌈(1 + ϵ)B⌉ + 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.

KW - Bounded degree spanning tree

KW - Crossing spanning tree

KW - Fast approximation algorithms

KW - Swap rounding

UR - http://www.scopus.com/inward/record.url?scp=85115664103&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85115664103&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs-APPROX/RANDOM.2021.24

DO - 10.4230/LIPIcs-APPROX/RANDOM.2021.24

M3 - Conference contribution

AN - SCOPUS:85115664103

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021

A2 - Wootters, Mary

A2 - Sanita, Laura

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 24th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2021 and 25th International Conference on Randomization and Computation, RANDOM 2021

Y2 - 16 August 2021 through 18 August 2021

ER -