Please use this identifier to cite or link to this item: http://dspace.mediu.edu.my:8181/xmlui/handle/1721.1/5394
Title: Nonlinear Formations and Improved Randomized Approximation Algorithms for Multiway and Multicut Problems
Issue Date: 9-Oct-2013
Publisher: Massachusetts Institute of Technology, Operations Research Center
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.
URI: http://koha.mediu.edu.my:8181/xmlui/handle/1721
Other Identifiers: http://hdl.handle.net/1721.1/5394
Appears in Collections:MIT Items

Files in This Item:
There are no files associated with this item.


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.