<p>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.</p>

<p>The <a href="http://books.google.com/books?id=Mhf4Zmq1Q3cC&amp;lpg=PA181&amp;dq=max%20cut%20poljak&amp;pg=PA181#v=onepage&amp;q&amp;f=false" rel="noreferrer">survey</a> 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.</p>

<p>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.</p>

<p>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: <a href="http://dx.doi.org/10.1145/237814.237980" rel="noreferrer">http://dx.doi.org/10.1145/237814.237980</a> (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: <a href="http://arxiv.org/abs/1008.3938" rel="noreferrer">http://arxiv.org/abs/1008.3938</a>.</p>

CC BY-SA 3.0
2011-06-08T08:04:06.613Z
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.
singhsumit
CC BY-SA 3.0
2011-06-08T17:26:41.267Z
@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
Sasho Nikolov
CC BY-SA 4.0
2018-05-10T19:18:37.210Z
@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?
Turbo
CC BY-SA 4.0
2018-05-10T23:38:42.647Z
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.)
Sasho Nikolov
CC BY-SA 4.0
2020-02-13T06:36:37.233Z
@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$?
Turbo
CC BY-SA 3.0
2011-06-08T01:06:16.323Z
2011-06-08T04:13:45.593Z
2011-06-08T04:13:45.593Z
Sasho Nikolov
<p>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).</p>

CC BY-SA 3.0
2011-06-08T13:22:45.630Z
Your title includes SDP but the body of your question does not. Are you interested in SDPs for Max-Cut or not?
Tyson Williams
<ds.algorithms><approximation-algorithms><linear-programming><max-cut><integrality-gap>
Max-cut via linear programming or sdp
singhsumit
# Max-cut via linear programming or sdp

(Asked by: username_0 on 2011-06-07)

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).

**Tags:** ds.algorithms, approximation-algorithms, linear-programming, max-cut, integrality-gap
> **Comments:**
> **username_1**: Your title includes SDP but the body of your question does not. Are you interested in SDPs for Max-Cut or not?  

---

## 1 answers

### Answer by username_2 on 2011-06-08. Score: 8 | Accepted answer

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](http://books.google.com/books?id=Mhf4Zmq1Q3cC&lpg=PA181&dq=max%20cut%20poljak&pg=PA181#v=onepage&q&f=false) 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>.

> **Comments:**
> **username_0**: 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.  
> **username_2**: @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  
> **username_3**: @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?  
> **username_2**: 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.)  
> **username_3**: @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$?  

---

