Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/44907
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
Source: 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.

Page view(s)

64
checked on Jan 12, 2018

Google ScholarTM

Check


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