Please use this identifier to cite or link to this item:
Title: Analysis of LP relaxations for multiway and multicut problems
Authors: Bertsimas, D.
Teo, C.-P. 
Vohra, R.
Keywords: LP relaxation
Multicut problems
Randomized rounding
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
ISSN: 00283045
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 Aug 19, 2019

Google ScholarTM


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