A tight example for approximation ratio 5 for covering small cuts by the primal-dual method

2025/12/09 by Nutov, Zeev
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2512.08350

openalex publication_date 2025/12/09 · openalex created_date 2025/12/11 · openalex updated_date 2026/07/28

Abstract

In the Small Cuts Cover problem we seek to cover by a min-cost edge-set the set family of cuts of size/capacity

Citations

• A Bad Example for Jain's Iterative Rounding Theorem for the Cover Small Cuts Problem
• Tight analysis of the primal-dual method for edge-covering pliable set families
• Improved Approximation Algorithms by Generalizing the Primal-Dual Method Beyond Uncrossable Functions

Related

• Tight analysis of the primal-dual method for edge-covering pliable set families
• Improved approximation ratio for covering pliable set families
• Approximating Small Sparse Cuts
• Preventing Small (s,t)-Cuts by Protecting Edges
• A parallel algorithm for minimum weight set cover with small neighborhood property