Nonlinear Formations and Improved Randomized Approximation Algorithms for Multiway and Multicut Problems
We introduce nonlinear formulations of the multiway cut and multicut problems. By simple linearizations of these formulations we derive several well known formulations and valid inequalities as well as several new ones. Through these formulations we establish a connection between the multiway cut an...
| Main Authors: | , , |
|---|---|
| Format: | Working Paper |
| Language: | en_US |
| Published: |
Massachusetts Institute of Technology, Operations Research Center
2004
|
| Online Access: | http://hdl.handle.net/1721.1/5394 |