Breaching the 2-approximation barrier for the forest augmentation problem
Fabrizio Grandoni, Afrouz Jabal Ameli, Vera Traub · 2022
The basic goal of survivable network design is to build cheap networks that guarantee the connectivity of certain pairs of nodes despite the failure of a few edges or nodes. A celebrated result by Jain [Combinatorica'01] provides a 2-approximation for a wide class of these problems. However nothing better is known even for very basic special cases, raising the natural question whether any improved approximation factor is possible at all.