๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Analysis of LP relaxations for multiway and multicut problems

โœ Scribed by Bertsimas, Dimitris; Teo, Chung-Piaw; Vohra, Rakesh

Publisher
John Wiley and Sons
Year
1999
Tongue
English
Weight
137 KB
Volume
34
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

โœฆ Synopsis

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.

๐Ÿ“œ SIMILAR VOLUMES

Lp estimates of solutions tomixed bounda
Lp estimates of solutions tomixed boundary value problems for the Stokes system in polyhedral domains
โœ V. Maz'ya; J. Rossmann ๐Ÿ“‚ Article ๐Ÿ“… 2007 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 497 KB ๐Ÿ‘ 1 views

## Abstract A mixed boundary value problem for the Stokes system in a polyhedral domain is considered. Here different boundary conditions (in particular, Dirichlet, Neumann, free surface conditions) are prescribed on the faces of the polyhedron. The authors prove the existence of solutions in (weig