The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set

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)

zbMATH Keywords

stable set polytopecliquerandom graphsemidefinite relaxationlift-and-project

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Semidefinite programming (90C22) Combinatorial optimization (90C27) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (17)

Isotonic regression with unknown permutations: statistics, computation and adaptation ⋮ Semidefinite and Linear Programming Integrality Gaps for Scheduling Identical Machines ⋮ Optimal detection of sparse principal components in high dimension ⋮ Finding one community in a sparse graph ⋮ Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation ⋮ Towards strong nonapproximability results in the Lovász-Schrijver hierarchy ⋮ Improved Approximation Guarantees through Higher Levels of SDP Hierarchies ⋮ A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem ⋮ Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra ⋮ Finding Hidden Cliques in Linear Time with High Probability ⋮ On linear and semidefinite programming relaxations for hypergraph matching ⋮ On the hardness of designing public signals ⋮ Semidefinite and linear programming integrality gaps for scheduling identical machines ⋮ Inapproximability of NP-Complete Variants of Nash Equilibrium ⋮ Sherali-adams strikes back ⋮ Unnamed Item ⋮ Dynamic node packing

This page was built for publication: The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set