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.