Please use this identifier to cite or link to this item:
Title: The parsimonious property of cut covering problems and its applications
Authors: Bertsimas, D.
Teo, C. 
Keywords: Cutset formulations
Integer programming
LP relaxations
Parsimonious property
Issue Date: 1997
Citation: Bertsimas, D.,Teo, C. (1997). The parsimonious property of cut covering problems and its applications. Operations Research Letters 21 (3) : 123-132. ScholarBank@NUS Repository.
Abstract: 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 earlier work by Goemans and Bertsimas (1993). 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. © 1997 Elsevier Science B.V.
Source Title: Operations Research Letters
ISSN: 01676377
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

checked on Sep 9, 2019

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.