A tight example for approximation ratio 5 for covering small cuts by the primal-dual method
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911331155705856 |
|---|---|
| author | Nutov, Zeev |
| author_facet | Nutov, Zeev |
| contents | In the Small Cuts Cover problem we seek to cover by a min-cost edge-set the set family of cuts of size/capacity $<k$ of a graph. Recently, Simmons showed that the primal-dual algorithm of Williamson, Goemans, Mihail, and Vazirani achieves approximation ratio $5$ for this problem, and asked whether this bound is tight. We will answer this question positively, by providing an example in which the ratio between the solution produced by the primal-dual algorithm and the optimum is arbitrarily close to $5$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_08350 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A tight example for approximation ratio 5 for covering small cuts by the primal-dual method Nutov, Zeev Data Structures and Algorithms In the Small Cuts Cover problem we seek to cover by a min-cost edge-set the set family of cuts of size/capacity $<k$ of a graph. Recently, Simmons showed that the primal-dual algorithm of Williamson, Goemans, Mihail, and Vazirani achieves approximation ratio $5$ for this problem, and asked whether this bound is tight. We will answer this question positively, by providing an example in which the ratio between the solution produced by the primal-dual algorithm and the optimum is arbitrarily close to $5$. |
| title | A tight example for approximation ratio 5 for covering small cuts by the primal-dual method |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2512.08350 |