New algorithm improves approximation for network design problems
An $n^{0.3+\varepsilon}$-Approximation for Steiner $k$-Forest
Data Structures and Algorithms
Summary
This paper tackles the challenge of connecting certain groups of points in a network with as little cost as possible, known as the Steiner k-Forest problem. The authors developed an improved method that provides better solutions than previous approaches for large networks. They also show that making the solutions significantly better for some cases would be extremely difficult due to connections with another hard problem called Densest k-Subgraph. This work helps understand the limits of how efficiently these complex network problems can be approximated.
What this means in practice
- •For network planners: Find near-optimal ways to connect multiple selected node groups in large networks more efficiently than before.
- •For software engineers in logistics: Improve routing and connectivity cost estimates for complex delivery or data distribution systems by using enhanced approximation methods.
A theory result. No direct application yet.
Authors
Eden Chlamtáč
Abstract
We give an $n^{0.3+\varepsilon}$-approximation algorithm for the Steiner $k$-Forest problem, for any constant $\varepsilon>0$. As a function of $n$, this improves over the $O(\min\{\sqrt{n},\sqrt{k}\})$-approximation of Gupta et al. [ESA'07, TALG'10] which has stood for nearly two decades for the general case, as well as the later $n^{0.448}$-approximation of Dinitz et. al [APPROX-RANDOM'14, TALG'17] for the uniform weight case. On the other hand, we show that, due to lower bounds on the Densest $k$-Subgraph problem, the $O(\sqrt k)$-approximation for Steiner $k$-Forest likely cannot be improved. Specifically, we show that for any sufficiently small $\varepsilon>0$, an $O(k^{1/2-\varepsilon})$-approximation for Steiner $k$-Forest would surpass known degree-$n^{Ω(\varepsilon^2)}$ Sum-of-Squares integrality gaps for Densest k-Subgraph and refute the corresponding dense-versus-random conjecture.