The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set
From MaRDI portal
Publication:4706196
DOI10.1137/S009753970240118XzbMath1021.05073MaRDI QIDQ4706196
Robert Krauthgamer, Uriel Feige
Publication date: 19 June 2003
Published in: SIAM Journal on Computing (Search for Journal in Brave)
05C80: Random graphs (graph-theoretic aspects)
90C22: Semidefinite programming
90C27: Combinatorial optimization
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Related Items
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem, Unnamed Item, Sherali-adams strikes back, Finding Hidden Cliques in Linear Time with High Probability, Optimal detection of sparse principal components in high dimension, Towards strong nonapproximability results in the Lovász-Schrijver hierarchy, On linear and semidefinite programming relaxations for hypergraph matching, Finding one community in a sparse graph, Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation, Semidefinite and linear programming integrality gaps for scheduling identical machines, Dynamic node packing, Isotonic regression with unknown permutations: statistics, computation and adaptation, On the hardness of designing public signals, Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra, Inapproximability of NP-Complete Variants of Nash Equilibrium, Semidefinite and Linear Programming Integrality Gaps for Scheduling Identical Machines, Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
