Journal article
M.F. Anjos, H. Wolkowicz
Discrete Applied Mathematics, vol. 119(1-2), 2002, pp. 79-106
Discrete Applied Mathematics, vol. 119(1-2), 2002, pp. 79-106
Semantic Scholar
DBLP
DOI
Cite
Cite
APA
Click to copy
Anjos, M. F., & Wolkowicz, H. (2002). Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem. Discrete Applied Mathematics, 119(1-2), 79–106. https://doi.org/10.1016/S0166-218X(01)00266-9
Chicago/Turabian
Click to copy
Anjos, M.F., and H. Wolkowicz. “Strengthened Semidefinite Relaxations via a Second Lifting for the Max-Cut Problem.” Discrete Applied Mathematics 119, no. 1-2 (2002): 79–106.
MLA
Click to copy
Anjos, M. F., and H. Wolkowicz. “Strengthened Semidefinite Relaxations via a Second Lifting for the Max-Cut Problem.” Discrete Applied Mathematics, vol. 119, no. 1-2, 2002, pp. 79–106, doi:10.1016/S0166-218X(01)00266-9.
BibTeX Click to copy
@article{m2002a,
title = {Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem},
year = {2002},
issue = {1-2},
journal = {Discrete Applied Mathematics},
pages = {79-106},
volume = {119},
doi = {10.1016/S0166-218X(01)00266-9},
author = {Anjos, M.F. and Wolkowicz, H.}
}
Abstract
In this paper we study two strengthened semidefinite programming relaxations for the Max-Cut problem. Our results hold for every instance of Max-Cut; in particular, we make no assumptions about the edge weights. We prove that the first relaxation provides a strengthening of the Goemans–Williamson relaxation. The second relaxation is a further tightening of the first one and we prove that its feasible set corresponds to a convex set that is larger than the cut polytope but nonetheless is strictly contained in the intersection of the elliptope and the metric polytope. Both relaxations are obtained using Lagrangian relaxation. Hence, our results also exemplify the strength and flexibility of Lagrangian relaxation for obtaining a variety of SDP relaxations with different properties.
We also address some practical issues in the solution of these SDP relaxations. Because Slater's constraint qualification fails for both of them, we project their feasible sets onto a lower dimensional space in a way that does not affect the sparsity of these relaxations but guarantees Slater's condition. Some preliminary numerical results are included.