A tight example for approximation ratio 5 for covering small cuts by the primal-dual method
By: Zeev Nutov
Potential Business Impact:
Finds the cheapest way to cut a network.
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$.
Similar Papers
Tight analysis of the primal-dual method for edge-covering pliable set families
Data Structures and Algorithms
Finds better ways to connect things in networks.
A Bad Example for Jain's Iterative Rounding Theorem for the Cover Small Cuts Problem
Data Structures and Algorithms
Finds cheaper ways to protect computer networks.
Approximation schemes for covering and packing mixed-integer programs with a fixed number of constraints
Data Structures and Algorithms
Solves hard math problems faster for businesses.