Improved approximation ratio for covering pliable set families
<|reference_start|>Improved approximation ratio for covering pliable set families: A classic result of Williamson, Goemans, Mihail, and Vazirani [STOC 1993: 708-717] states that the problem of covering an uncrossable set family by a min-cost edge set admits approximation ratio $2$, by a primal-dual algorithm with a reverse delete phase. Recently, Bansal, Cheriyan, Grout, and Ibrahimpur [ICALP 2023: 15:1-15:19] showed that this algorithm achieves approximation ratio $16$ for a larger class of set families, that have much weaker uncrossing properties. In this paper we will refine their analysis and show an approximation ratio of $10$. This also improves approximation ratios for several variants of the Capacitated $k$-Edge Connected Spanning Subgraph problem.<|reference_end|>
@article{nutov2024improved,
    title={Improved approximation ratio for covering pliable set families},
    author={Zeev Nutov},
    journal={arXiv preprint arXiv:2404.00683},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.00683},
    primaryClass={cs.DS}
}