SIAM Journal on Optimization · 2002 · 329 citations · 17 references
ComputingComputer ScienceMathematicsAlgorithmsOptimizationTheory Of ComputationApproximation AlgorithmsCombinatorial OptimizationLinear ProgrammingMatrix ComputationRobust OptimizationStabilityApproximation TheoryConic ProgrammingLinear Programming RelaxationsRobust Linear ProgrammingSemidefinite ProgrammingStability NumberStable SetSuccessive Approximations
Lovász and Schrijver [SIAM J. Optim., 1 (1991), pp. 166–190] showed how to formulate increasingly tight approximations of the stable set polytope of a graph by solving semidefinite programs (SDPs) of increasing size (lift-and-project method). In this paper we present a similar idea. We show how the stability number can be computed as the solution of a conic linear program (LP) over the cone of copositive matrices. Subsequently, we show how to approximate the copositive cone ever more closely via a hierarchy of linear or semidefinite programs of increasing size (liftings). The latter idea is based on recent work by Parrilo [Structured Semidefinite Programs and Semi-algebraic Geometry Methods in Robustness and Optimization, Ph.D. thesis, California Institute of Technology, Pasadena, CA, 2000]. In this way we can compute the stability number α(G) of any graph G(V, E) after at most α(G)2 successive liftings for the LP-based approximations. One can compare this to the n - α(G) - 1 bound for the LP-based lift-and-project scheme of Lovász and Schrijver. Our approach therefore requires fewer liftings for families of graphs where a(G) < O(√n). We show that the first SDP-based approximation for α(G) in our series of increasingly tight approximations coincides with the ϑ’function of Schrijver [IEEE Trans. Inform. Theory, 25 (1979), pp. 425–429]. We further show that the second approximation is tight for complements of triangle-free graphs and for odd cycles.
17
On the Shannon capacity of a graph
László Lovász · IEEE Transactions on Information Theory · 1979 · 1.7K citations
Clique is hard to approximate within n1−ε
Johan Håstad · Acta Mathematica · 1999 · 1.4K citations · Full text