Geometry of Semidefinite Max-Cut Relaxations via Matrix Ranks

Miguel F. Anjos () and Henry Wolkowicz ()
Additional contact information
Miguel F. Anjos: University of Waterloo
Henry Wolkowicz: University of Waterloo

Journal of Combinatorial Optimization, 2002, vol. 6, issue 3, No 2, 237-270

Abstract: Abstract Semidefinite programming (SDP) relaxations are proving to be a powerful tool for finding tight bounds for hard discrete optimization problems. This is especially true for one of the easier NP-hard problems, the Max-Cut problem (MC). The well-known SDP relaxation for Max-Cut, here denoted SDP1, can be derived by a first lifting into matrix space and has been shown to be excellent both in theory and in practice. Recently the present authors have derived a new relaxation using a second lifting. This new relaxation, denoted SDP2, is strictly tighter than the relaxation obtained by adding all the triangle inequalities to the well-known relaxation. In this paper we present new results that further describe the remarkable tightness of this new relaxation. Let $$F_n $$ denote the feasible set of SDP2 for the complete graph with n nodes, let F n denote the appropriately defined projection of $$F_n $$ into $$S^n $$ , the space of real symmetric n × n matrices, and let C n denote the cut polytope in $$S^n $$ . Further let $$Y \in F_n $$ be the matrix variable of the SDP2 relaxation and X ∈ F n be its projection. Then for the complete graph on 3 nodes, F 3 = C 3 holds. We prove that the rank of the matrix variable $$Y \in F_3 $$ of SDP2 completely characterizes the dimension of the face of the cut polytope in which the corresponding matrix X lies. This shows explicitly the connection between the rank of the variable Y of the second lifting and the possible locations of the projected matrix X within C 3. The results we prove for n = 3 cast further light on how SDP2 captures all the structure of C 3, and furthermore they are stepping stones for studying the general case n ≥ 4. For this case, we show that the characterization of the vertices of the cut polytope via rank Y = 1 extends to all n ≥ 4. More interestingly, we show that the characterization of the one-dimensional faces via rank Y = 2 also holds for n ≥ 4. Furthermore, we prove that if rank Y = 2 for n ≥ 3, then a simple algorithm exhibits the two rank-one matrices (corresponding to cuts) which are the vertices of the one-dimensional face of the cut polytope where X lies.

Keywords: semidefinite programming; discrete optimization; Lagrangian relaxation; Max-Cut problem (search for similar items in EconPapers)
Date: 2002
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1023/A:1014895808844 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:6:y:2002:i:3:d:10.1023_a:1014895808844

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/A:1014895808844

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().