License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.24
URN: urn:nbn:de:0030-drops-147177
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14717/
Go to the corresponding LIPIcs Volume Portal

Chekuri, Chandra ; Quanrud, Kent ; Torres, Manuel R.

Fast Approximation Algorithms for Bounded Degree and Crossing Spanning Tree Problems

pdf-format:
LIPIcs-APPROX24.pdf (0.8 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{chekuri_et_al:LIPIcs.APPROX/RANDOM.2021.24,
  author =	{Chekuri, Chandra and Quanrud, Kent and Torres, Manuel R.},
  title =	{{Fast Approximation Algorithms for Bounded Degree and Crossing Spanning Tree Problems}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{24:1--24:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14717},
  URN =		{urn:nbn:de:0030-drops-147177},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.24},
  annote =	{Keywords: bounded degree spanning tree, crossing spanning tree, swap rounding, fast approximation algorithms}
}

Keywords: bounded degree spanning tree, crossing spanning tree, swap rounding, fast approximation algorithms
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Issue Date: 2021
Date of publication: 15.09.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI