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)
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Convex programming (90C25) Integer programming (90C10) Combinatorial optimization (90C27) Designs and configurations (05B99)
Related Items
Exact MIP-based approaches for finding maximum quasi-cliques and dense subgraphs, An edge-reduction algorithm for the vertex cover problem, Fast First-Order Algorithms for Packing–Covering Semidefinite Programs, A Derivation of Lovász' Theta via Augmented Lagrange Duality, On a restricted cross-intersection problem, Semidefinite programming in combinatorial optimization, Spectral bounds for the independence ratio and the chromatic number of an operator, Vertex Cover in Graphs with Locally Few Colors, An axiomatic duality framework for the theta body and related convex corners, Convex Relaxations and Integrality Gaps, Hypercontractive inequalities via SOS, and the Frankl--Rödl graph, Strong and weak edges of a graph and linkages with the vertex cover problem, Specified intersections
