The Parsimonious Property of Cut Covering Problems and Its Applications: January, 1994 (Classic Reprint)

Excerpt from The Parsimonious Property of Cut Covering Problems and Its Applications: January, 1994

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 deep structural property, the parsimonious property, generalizing earlier work by Goemans and Bertsimas [3]. We identify two set of conditions for the parsimonious property to hold and offer two proof techniques based on combinatorial and algebraic arguments. We examine several consequences of the parsimonious property in proving monotonicity properties of LP relaxations, giving genuinely simple proofs of integrality of polyhedra in this class, offering a unifying understanding of results in disjoint path problems and in the approximability of problems in the class. We also propose a new proof method that utilizes the parsimonious property for establishing worst case bounds between the gap of the IP and LP values. Our analysis unifies and extends a large set of results in combinatorial optimization.

About the Publisher

Forgotten Books publishes hundreds of thousands of rare and classic books. Find more at www.forgottenbooks.com

This book is a reproduction of an important historical work. Forgotten Books uses state-of-the-art technology to digitally reconstruct the work, preserving the original format whilst repairing imperfections present in the aged copy. In rare cases, an imperfection in the original, such as a blemish or missing page, may be replicated in our edition. We do, however, repair the vast majority of imperfections successfully; any imperfections that remain are intentionally left to preserve the state of such historical works.