Tighter linear and semidefinite relaxations for max-cut based on the Lov\'asz-Schrijver lift-and-project procedure.
SIAM Journal on Optimization , Volume 12 - Issue 2 p. 345- 375
|linear relaxation, semidefinite relaxation, lift-and-project, cut polytope, stable set polytope|
|Graphs and linear algebra (matrices, eigenvalues, etc.) (msc 05C50), Hermitian, skew-Hermitian, and related matrices (msc 15B57), Special polytopes (linear programming, centrally symmetric, etc.) (msc 52B12), Semidefinite programming (msc 90C22), Combinatorial optimization (msc 90C27)|
|Logistics (theme 3)|
|SIAM Journal on Optimization|
|Organisation||Networks and Optimization|
Laurent, M. (2001). Tighter linear and semidefinite relaxations for max-cut based on the Lov\'asz-Schrijver lift-and-project procedure. SIAM Journal on Optimization, 12(2), 345–375.