Geometry of semidefinite Max-Cut relaxations via matrix ranks

DOI10.1023/A:1014895808844zbMath1018.90030MaRDI QIDQ1610658

Miguel F. Anjos, Henry Wolkowicz

Publication date: 20 August 2002

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

zbMATH Keywords

Lagrangian relaxationsemidefinite programmingdiscrete optimizationMax-Cut problem

Mathematics Subject Classification ID

Semidefinite programming (90C22) Combinatorial optimization (90C27)

Related Items (5)

Structure methods for solving the nearest correlation matrix problem ⋮ An explicit semidefinite characterization of satisfiability for Tseitin instances on toroidal grid graphs ⋮ A strengthened Barvinok-Pataki bound on SDP rank ⋮ Semidefinite programming for discrete optimization and matrix completion problems ⋮ An improved semidefinite programming relaxation for the satisfiability problem

Uses Software

• COL

This page was built for publication: Geometry of semidefinite Max-Cut relaxations via matrix ranks