Please use this identifier to cite or link to this item:
|Title:||Analysis of LP relaxations for multiway and multicut problems|
|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.|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Feb 9, 2019
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.