论文标题
有限程度和跨越树问题的快速近似算法
Fast Approximation Algorithms for Bounded Degree and Crossing Spanning Tree Problems
论文作者
论文摘要
我们开发了有界MST问题（BD-MST）的最低成本版本的快速近似算法及其概括的交叉跨越树问题（Crossing-ST）。我们通过乘量重量更新（MWU）技术将基础LP在$（1+ε）$近似因子内解决。尤其是一种接近线性的时间算法，该算法输出估计$ b $，因此$ b \ le b^* \ le \ lceil（1 +ε）b \ rceil +1 $，其中$ b^* $是给定图的跨度树的最小程度。为了圆形分数解决方案，在我们的主要技术贡献中，我们描述了图表的跨性别树多型中互换的快速近线性时间实现。分数解决方案还可以用于稀疏输入图，后者又可以用来加快现有组合算法的速度。总之，这些想法导致近似算法的显着更快。此外，图形矩阵中用于交换舍入的快速算法是具有其他应用程序的通用工具，包括对TSP和下函数最大化。
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 \le B^* \le \lceil (1+ε)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.
