Semidefinite bounds for the stability number of a graph via sums of squares of polynomials

DOI10.1007/S10107-006-0062-8zbMath1113.90117OpenAlexW4246855957MaRDI QIDQ877197

Monique Laurent, Nebojša Gvozdenović

Publication date: 19 April 2007

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-006-0062-8

Mathematics Subject Classification ID

Semidefinite programming (90C22) Combinatorial optimization (90C27)

Related Items (13)

Symmetry in RLT-type relaxations for the quadratic assignment and standard quadratic optimization problems ⋮ Mathematical Programming Models and Exact Algorithms ⋮ Computing the distance between the linear matrix pencil and the completely positive cone ⋮ On the exactness of sum-of-squares approximations for the cone of \(5 \times 5\) copositive matrices ⋮ Finite Convergence of Sum-of-Squares Hierarchies for the Stability Number of a Graph ⋮ A note on the Lasserre hierarchy for different formulations of the maximum independent set problem ⋮ Approximation hierarchies for copositive cone over symmetric cone and their comparison ⋮ Sum of squares basis pursuit with linear and second order cone programming ⋮ Independent sets in graphs ⋮ Sum-of-squares certificates for copositivity via test states ⋮ A new branch-and-bound algorithm for standard quadratic programming problems ⋮ Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs ⋮ A Comprehensive Analysis of Polyhedral Lift-and-Project Methods

Uses Software

• QUALEX

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Strengthened semidefinite programming bounds for codes
• Geometric algorithms and combinatorial optimization
• Solving standard quadratic optimization problems via linear, semidefinite and copositive pro\-gramming
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• A new trust region technique for the maximum weight clique problem
• Global Optimization with Polynomials and the Problem of Moments
• Approximation of the Stability Number of a Graph via Copositive Programming
• New Code Upper Bounds From the Terwilliger Algebra and Semidefinite Programming
• A comparison of the Delsarte and Lovász bounds
• Sums of even powers of real linear forms
• Cones of Matrices and Set-Functions and 0–1 Optimization
• On the Shannon capacity of a graph
• Semidefinite Programming
• Optimization of Polynomials on Compact Semialgebraic Sets
• Maxima for Graphs and a New Proof of a Theorem of Turán
• Computing the Stability Number of a Graph Via Linear and Semidefinite Programming
• LMI Approximations for Cones of Positive Semidefinite Forms
• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
• Handbook of semidefinite programming. Theory, algorithms, and applications

This page was built for publication: Semidefinite bounds for the stability number of a graph via sums of squares of polynomials