3/2-Approximation for the Forest Augmentation Problem

2024/07/15 by Ali Çivril, Çivril, Ali
#cs.DS

paper · pdf · doi:10.48550/arxiv.2407.11101

Abstract

We describe a (3)/(2)-approximation algorithm for the Forest Augmentation Problem (\textsfFAP), which is a special case of the Weighted 2-Edge-Connected Spanning Subgraph Problem (\textsfWeighted 2-ECSS). This significantly improves upon the previous best ratio 1.9973, and proceeds toward the goal of a (3)/(2)-approximation algorithm for \textsfWeighted 2-ECSS.

Related

• Improved Approximation Algorithms for Path and Forest Augmentation via a Novel Relaxation
• Breaching the 2-Approximation Barrier for the Forest Augmentation Problem
• A Better-Than-2 Approximation for Weighted Tree Augmentation
• A (3)/(2)-Approximation Algorithm for Tree Augmentation via Chvátal-Gomory Cuts
• Fast Distributed Approximation for TAP and 2-Edge-Connectivity