The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set
From MaRDI portal
Publication:4706196
DOI10.1137/S009753970240118XzbMath1021.05073MaRDI QIDQ4706196
Publication date: 19 June 2003
Published in: SIAM Journal on Computing (Search for Journal in Brave)
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
