# Max-cut via linear programming or sdp

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

• Your title includes SDP but the body of your question does not. Are you interested in SDPs for Max-Cut or not? – Tyson Williams Jun 8 '11 at 13:22

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.
• 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 May 10 '18 at 23:38