Analysis of LP relaxations for multiway and multicut problems
Dimitris Bertsimas, Chung‐Piaw Teo, Rakesh Vohra · Networks · 1999
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