The parsimonious property of cut covering problems and its applications

We consider the analysis of linear programming relaxations of a large class of combinatorial problems that can be formulated as problems of covering cuts, including the Steiner tree, the traveling salesman, the vehicle routing, the matching, the T-join and the survivable network design problem, to name a few. We prove that all of the problems in the class satisfy a nice structural property, the parsimonious property, generalizing in earlier work by Goemans and Bertsimas. We utilize the parsimonious property to establish worst-case bounds between the gap of the IP and LP values for the class of 0–1 proper functions, leading to a new 2-approximation algorithm for this class of problems. We also extend the parsimonious property to a class of cut-covering problems that model certain instances of the edge-disjoint path problem.