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.
|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.
checked on Sep 9, 2019
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.