4.3 Article

A tight semidefinite relaxation of the MAX CUT problem

Journal

JOURNAL OF COMBINATORIAL OPTIMIZATION
Volume 7, Issue 3, Pages 237-245

Publisher

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

Primary Rating

4.3
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available