pipette
ENEnglish

An -Approximation for Steiner -Forest

Eden Chlamt\'a\v{c}

Preprint

En palabras de los autores

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.

Resultado principalLimitación que admiten los autores

Apareció: jueves, 8 de octubre. arXiv. Preprint, todavía sin revisión por pares.