Premium
Analysis of LP relaxations for multiway and multicut problems
Author(s) -
Bertsimas Dimitris,
Teo ChungPiaw,
Vohra Rakesh
Publication year - 1999
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199909)34:2<102::aid-net3>3.0.co;2-x
Subject(s) - simple (philosophy) , mathematics , rounding , set (abstract data type) , independent set , computer science , mathematical optimization , combinatorics , algorithm , graph , philosophy , epistemology , programming language , operating system
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