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 |
| _version_ | 1826197870946025472 |
|---|---|
| author | Bertsimas, Dimitris J. Teo, Chungpiaw Vohra, Rakesh |
| author_facet | Bertsimas, Dimitris J. Teo, Chungpiaw Vohra, Rakesh |
| author_sort | Bertsimas, Dimitris J. |
| collection | MIT |
| description | 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 and the maximum weighted independent set problem that leads to the study of the tightness of several LP formulations for the multiway cut problem through the theory of perfect graphs. We also introduce a new randomized rounding argument to study the worst case bound of these formulations, obtaining a new bound of 2a(H)(1 - ) for the multicut problem, where ac(H) is the size of a maximum independent set in the demand graph H. |
| first_indexed | 2024-09-23T10:54:46Z |
| format | Working Paper |
| id | mit-1721.1/5394 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:54:46Z |
| publishDate | 2004 |
| publisher | Massachusetts Institute of Technology, Operations Research Center |
| record_format | dspace |
| spelling | mit-1721.1/53942019-04-10T10:36:42Z Nonlinear Formations and Improved Randomized Approximation Algorithms for Multiway and Multicut Problems Bertsimas, Dimitris J. Teo, Chungpiaw Vohra, Rakesh 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 and the maximum weighted independent set problem that leads to the study of the tightness of several LP formulations for the multiway cut problem through the theory of perfect graphs. We also introduce a new randomized rounding argument to study the worst case bound of these formulations, obtaining a new bound of 2a(H)(1 - ) for the multicut problem, where ac(H) is the size of a maximum independent set in the demand graph H. 2004-05-28T19:37:26Z 2004-05-28T19:37:26Z 1995-06 Working Paper http://hdl.handle.net/1721.1/5394 en_US Operations Research Center Working Paper ; OR 308-95 1318398 bytes application/pdf application/pdf Massachusetts Institute of Technology, Operations Research Center |
| spellingShingle | Bertsimas, Dimitris J. Teo, Chungpiaw Vohra, Rakesh Nonlinear Formations and Improved Randomized Approximation Algorithms for Multiway and Multicut Problems |
| title | Nonlinear Formations and Improved Randomized Approximation Algorithms for Multiway and Multicut Problems |
| title_full | Nonlinear Formations and Improved Randomized Approximation Algorithms for Multiway and Multicut Problems |
| title_fullStr | Nonlinear Formations and Improved Randomized Approximation Algorithms for Multiway and Multicut Problems |
| title_full_unstemmed | Nonlinear Formations and Improved Randomized Approximation Algorithms for Multiway and Multicut Problems |
| title_short | Nonlinear Formations and Improved Randomized Approximation Algorithms for Multiway and Multicut Problems |
| title_sort | nonlinear formations and improved randomized approximation algorithms for multiway and multicut problems |
| url | http://hdl.handle.net/1721.1/5394 |
| work_keys_str_mv | AT bertsimasdimitrisj nonlinearformationsandimprovedrandomizedapproximationalgorithmsformultiwayandmulticutproblems AT teochungpiaw nonlinearformationsandimprovedrandomizedapproximationalgorithmsformultiwayandmulticutproblems AT vohrarakesh nonlinearformationsandimprovedrandomizedapproximationalgorithmsformultiwayandmulticutproblems |