Please use this identifier to cite or link to this item:
|Title:||Analysis of LP relaxations for multiway and multicut problems||Authors:||Bertsimas, D.
|Issue Date:||1999||Citation:||Bertsimas, D.,Teo, C.-P.,Vohra, R. (1999). Analysis of LP relaxations for multiway and multicut problems. Networks 34 (2) : 102-114. ScholarBank@NUS Repository.||Abstract:||We introduce in this paper an exact nonlinear formulation of the multiway cut problem. By simple linearizations of this formulation, we derive several well-known and new formulations for the problem. We further establish a connection between the multiway cut and the maximum-weighted independent set problem. This leads to the study of several instances of the multiway cut problem through the theory of perfect graphs. We also introduce a new randomized rounding argument to study the sharpness of these formulations. © 1999 John Wiley & Sons, Inc. Networks 34: 102-114, 1999.||Source Title:||Networks||URI:||http://scholarbank.nus.edu.sg/handle/10635/44907||ISSN:||00283045|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Aug 19, 2019
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.