Semidefinite bounds for the stability number of a graph via sums of squares of polynomials
From MaRDI portal
Publication:877197
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
Related Items
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, 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
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
