Journal
JOURNAL OF COMBINATORIAL OPTIMIZATION
Volume 7, Issue 3, Pages 237-245Publisher
KLUWER ACADEMIC PUBL
DOI: 10.1023/A:1027364420370
Keywords
MAX CUT problem; semidefinite relaxation; cut polytope; metric polytope
Ask authors/readers for more resources
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 also it satisfy Slater constraint qualification ( strict feasibility).
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available