Author(s)

Rakesh Vohra

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
Date Published: 1999
Citations: Vohra, Rakesh. 1999. Analysis of LP relaxations for multiway and multicut problems. Networks. (2)102-114.