×

zbMATH — the first resource for mathematics

A tight semidefinite relaxation of the MAX CUT problem. (English) Zbl 1175.90335
Summary: We obtain a tight semidefinite relaxation of the MAX CUT problem which improves several previous SDP relaxation in the literature. Not only is it a strict improvement over the SDP relaxation obtained by adding all the triangle inequalities to the well-known SDP relaxation, but it also satisfies the Slater constraint qualification (strict feasibility).

MSC:
90C27 Combinatorial optimization
Software:
SDPpack
PDF BibTeX XML Cite
Full Text: DOI