Copositive programming motivated bounds on the stability and the chromatic numbers
From MaRDI portal
Publication:847835
DOI10.1007/S10107-008-0233-XzbMATH Open1194.90109OpenAlexW2123082562MaRDI QIDQ847835FDOQ847835
Authors: Igor Dukanovic, Franz Rendl 
Publication date: 19 February 2010
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-008-0233-x
Recommendations
- Approximation of the stability number of a graph via copositive programming
- Semidefinite programming relaxations for graph coloring and maximal clique problems
- Strengthening the Lovász \(\theta(\overline G)\) bound for graph coloring
- The Operator $\Psi$ for the Chromatic Number of a Graph
- Computing Semidefinite Programming Lower Bounds for the (Fractional) Chromatic Number Via Block-Diagonalization
Programming involving graphs or networks (90C35) Semidefinite programming (90C22) Coloring of graphs and hypergraphs (05C15)
Cites Work
- Some NP-complete problems in quadratic and nonlinear programming
- Approximate graph coloring by semidefinite programming
- On the Shannon capacity of a graph
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Symmetry groups, semidefinite programs, and sums of squares
- Approximation of the stability number of a graph via copositive programming
- Semidefinite optimization
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Computing the Stability Number of a Graph Via Linear and Semidefinite Programming
- Copositive and semidefinite relaxations of the quadratic assignment problem
- Reduction of symmetric semidefinite programs using the regular \(\ast\)-representation
- Solving standard quadratic optimization problems via linear, semidefinite and copositive pro\-gramming
- The Operator $\Psi$ for the Chromatic Number of a Graph
- The sandwich theorem
- Title not available (Why is that?)
- A comparison of the Delsarte and Lovász bounds
- Strengthened semidefinite programming bounds for codes
- Aspects of semidefinite programming. Interior point algorithms and selected applications
- Title not available (Why is that?)
- Semidefinite programming relaxations for graph coloring and maximal clique problems
- On copositive programming and standard quadratic optimization problems
- Semidefinite programming and integer programming
- A semidefinite programming-based heuristic for graph coloring
- Computing Semidefinite Programming Lower Bounds for the (Fractional) Chromatic Number Via Block-Diagonalization
- Copositive realxation for genera quadratic programming
- Coloring -colorable graphs using relatively small palettes
- On NP-hardness of the clique partition -- independence number gap recognition and related problems
- Semidefinite Bounds for the Stability Number of a Graph via Sums of Squares of Polynomials
Cited In (30)
- Conic formulations of graph homomorphisms
- Some experiences with solving semidefinite programming relaxations of binary quadratic optimization models in computational biology
- On upper bounding Shannon capacity of graph through generalized conic programming
- A complete semidefinite algorithm for detecting copositive matrices and tensors
- Quadratic factorization heuristics for copositive programming
- Algebras, graphs and thetas
- A semidefinite relaxation algorithm for checking completely positive separable matrices
- Think co(mpletely)positive! Matrix properties, examples and a clustered bibliography on copositive optimization
- Matrix relaxations in combinatorial optimization
- Copositive optimization -- recent developments and applications
- On LP-based approximation for copositive formulation of stable set problem
- Semidefinite programming relaxations for graph coloring and maximal clique problems
- Exactness of Parrilo’s Conic Approximations for Copositive Matrices and Associated Low Order Bounds for the Stability Number of a Graph
- Approximation of the stability number of a graph via copositive programming
- A copositive formulation for the stability number of infinite graphs
- Conic approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone
- Finite convergence of sum-of-squares hierarchies for the stability number of a graph
- Completely positive reformulations for polynomial optimization
- Constraint selection in a build-up interior-point cutting-plane method for solving relaxations of the stable-set problem
- The CP-matrix approximation problem
- Copositivity cuts for improving SDP bounds on the clique number
- Copositive programming
- Title not available (Why is that?)
- Tightening a copositive relaxation for standard quadratic optimization problems
- Depth-first simplicial partition for copositivity detection, with an application to MaxClique
- Dual Hoffman bounds for the stability and chromatic numbers based on semidefinite programming
- The Operator $\Psi$ for the Chromatic Number of a Graph
- An axiomatic duality framework for the theta body and related convex corners
- Completely positive and completely positive semidefinite tensor relaxations for polynomial optimization
- Graph isomorphism: physical resources, optimization models, and algebraic characterizations
This page was built for publication: Copositive programming motivated bounds on the stability and the chromatic numbers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q847835)
