pipette
ESEspañol

An -Approximation for Steiner -Forest

Eden Chlamt\'a\v{c}

Preprint

In the authors' words

We give an -approximation algorithm for the Steiner -Forest problem, for any constant . As a function of , this improves over the -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 -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 -Subgraph problem, the -approximation for Steiner -Forest likely cannot be improved. Specifically, we show that for any sufficiently small , an -approximation for Steiner -Forest would surpass known degree- Sum-of-Squares integrality gaps for Densest k-Subgraph and refute the corresponding dense-versus-random conjecture.

Main resultLimitation the authors admit

Appeared: Thursday, October 8. arXiv. Preprint, not yet peer-reviewed.