The Lovász Theta Function and a Semidefinite Programming Relaxation of Vertex Cover
From MaRDI portal
Publication:4388988
DOI10.1137/S0895480195287541zbMath0910.90262MaRDI QIDQ4388988
Michel X. Goemans, Jon M. Kleinberg
Publication date: 11 May 1998
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
90C35: Programming involving graphs or networks
68Q25: Analysis of algorithms and problem complexity
90C25: Convex programming
90C10: Integer programming
90C27: Combinatorial optimization
05B99: Designs and configurations
Related Items
A Derivation of Lovász' Theta via Augmented Lagrange Duality, An edge-reduction algorithm for the vertex cover problem, On a restricted cross-intersection problem, Semidefinite programming in combinatorial optimization