Please use this identifier to cite or link to this item:
https://scholarbank.nus.edu.sg/handle/10635/44971
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 | URI: | http://scholarbank.nus.edu.sg/handle/10635/44971 | ISSN: | 01676377 |
Appears in Collections: | Staff Publications |
Show full item record
Files in This Item:
There are no files associated with this item.
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.