Key points are not available for this paper at this time.
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.
Zeev Nutov (Sun,) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: