I am looking for a linear programming formulation for the max-cut problem. My interest is to know about the primal - dual algorithm for max-cut. It would be nice if someone can tell me that what is the best ratio achieved via this approach. Please mention the formulation along with the integrality gap. Any other information/comments are invited. My primary interest includes to know about the alternate ways that lead to 0.8 approximation for max-cut or near to it (preferably via primal dual scheme).
$\begingroup$
$\endgroup$
1
-
2$\begingroup$ Your title includes SDP but the body of your question does not. Are you interested in SDPs for Max-Cut or not? $\endgroup$– Tyson WilliamsCommented Jun 8, 2011 at 13:22
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
Did you try to look this up? Max Cut might be the most well studies problem out there, with tons of information on it on the web.
The survey by Poljak from '95 has a lot on different LP relaxations of Max Cut and the relationships between them. He considers special cases in which the relaxations are integral or almost integral. There are numerous other bounds on Max Cut, as well as non-polyhedral relaxations. This survey is very old, but all known LPs for Max Cut have been known to be dead ends for many years: every known LP relaxation of Max Cut, including the ones mentioned by Poljak, has integrality gap 2. So they are no better starting point than the trivial randomized or greedy algorithms. LPs for Max Cut have been out of fashion at least since Goemans and Williamson's SDP paper.
Some newer results: de la Vega and Mathieu show that adding any constraints with bounded support to the standard LP relaxation leaves the integrality gap at 2 (http://portal.acm.org/citation.cfm?id=1283390). The same is true for $n^\delta$ rounds of the Sherali-Adams hierarchy (http://portal.acm.org/citation.cfm?id=1536455). So in a very strong sense LPs are no help for Max Cut.
On the other hand there is work on primal-dual algorithms for Max Cut based on the GW SDP. Klein and Lu gave a fast approximation for MaxCut that matches Goemans-Williamson: http://dx.doi.org/10.1145/237814.237980 (they use what is now known as the multiplicative weights method to solve the SDP). I don't know the details, but I know that Luca's approximation of Max Cut using eigenvectors is in some sense a dual of the GW SDP (http://arxiv.org/abs/0806.1978). The latest combinatorial random-walk based algorithm is based on Luca's: http://arxiv.org/abs/1008.3938.
answered Jun 8, 2011 at 1:06
-
$\begingroup$ thanks for references.. i had seen the results with integrality gap 2 and that with Sherali-Adams hierarchy though i couldn't understand fully the latter. I was basically interested in knowing some other approach more close primal dual approach for max-cut. Infact there was a paper on primal dual for sdp and i was wondering if people have results on that for maxcut which is comparable to 0.8 ratio for max-cut by goeman and williamson. $\endgroup$ Commented Jun 8, 2011 at 8:04
-
1$\begingroup$ @singhsumit: I recommend reading Luca's paper: it's wonderfully written, and is motivated by looking for a primal-dual algorithm for Max Cut. I was imprecise to say that the Klein-Lu technique (which is a case of multiplicative weights) is a primal-dual algorithm: it is based on a Lagrangian relaxation of the SDP, which has a primal-dual flavor, I think. Luca's algorithm actually is a primal-dual algorithm based on the SDP: he has a nice discussion of that in Section 6 in the arXiv paper. however, his algorithm doesn't match the GW ratio $\endgroup$ Commented Jun 8, 2011 at 17:26
-
$\begingroup$ @SashoNikolov 'He considers special cases in which the relaxations are integral' If there exists MAXCUT integral LP relaxations why would there be integrality gap and potential need for SDPs? $\endgroup$– TurboCommented May 10, 2018 at 19:18
-
$\begingroup$ They are integral in special cases: for example planar graphs or graphs not contractible to $K_5$. (BTW I don't think these LPs are of polynomial size, but they do have efficient separation oracles.) $\endgroup$ Commented May 10, 2018 at 23:38
-
$\begingroup$ @SashoNikolov $MAX-CUT$ has better than $16/17$ approximation under $NP$ hardness results while $UGC$ only gives $0.878$ guarantee. Is it possible perhaps to have $0.89$ approximation by violating only $UGC$ but not $P\neq NP$? $\endgroup$– TurboCommented Feb 13, 2020 at 6:36