Copositive programming motivated bounds on the stability and the chromatic numbers
From MaRDI portal
Publication:847835
DOI10.1007/S10107-008-0233-XzbMath1194.90109OpenAlexW2123082562MaRDI QIDQ847835
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
Programming involving graphs or networks (90C35) Semidefinite programming (90C22) Coloring of graphs and hypergraphs (05C15)
Related Items (21)
Algebras, graphs and thetas ⋮ Conic formulations of graph homomorphisms ⋮ Matrix Relaxations in Combinatorial Optimization ⋮ Tightening a copositive relaxation for standard quadratic optimization problems ⋮ Conic Approach to Quantum Graph Parameters Using Linear Optimization Over the Completely Positive Semidefinite Cone ⋮ Constraint selection in a build-up interior-point cutting-plane method for solving relaxations of the stable-set problem ⋮ Semidefinite programming relaxations for graph coloring and maximal clique problems ⋮ SOME EXPERIENCES WITH SOLVING SEMIDEFINITE PROGRAMMING RELAXATIONS OF BINARY QUADRATIC OPTIMIZATION MODELS IN COMPUTATIONAL BIOLOGY ⋮ Graph isomorphism: physical resources, optimization models, and algebraic characterizations ⋮ Copositive optimization -- recent developments and applications ⋮ Think co(mpletely)positive! Matrix properties, examples and a clustered bibliography on copositive optimization ⋮ Completely positive and completely positive semidefinite tensor relaxations for polynomial optimization ⋮ An axiomatic duality framework for the theta body and related convex corners ⋮ Quadratic factorization heuristics for copositive programming ⋮ The CP-Matrix Approximation Problem ⋮ A Complete Semidefinite Algorithm for Detecting Copositive Matrices and Tensors ⋮ Copositive Programming ⋮ Depth-first simplicial partition for copositivity detection, with an application to MaxClique ⋮ A semidefinite relaxation algorithm for checking completely positive separable matrices ⋮ On upper bounding Shannon capacity of graph through generalized conic programming ⋮ Completely positive reformulations for polynomial optimization
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Copositive and semidefinite relaxations of the quadratic assignment problem
- Semidefinite programming relaxations for graph coloring and maximal clique problems
- Strengthened semidefinite programming bounds for codes
- Reduction of symmetric semidefinite programs using the regular \(\ast\)-representation
- The sandwich theorem
- Aspects of semidefinite programming. Interior point algorithms and selected applications
- Solving standard quadratic optimization problems via linear, semidefinite and copositive pro\-gramming
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Symmetry groups, semidefinite programs, and sums of squares
- On NP-hardness of the clique partition -- independence number gap recognition and related problems
- A semidefinite programming-based heuristic for graph coloring
- Approximation of the Stability Number of a Graph via Copositive Programming
- Semidefinite optimization
- Semidefinite Bounds for the Stability Number of a Graph via Sums of Squares of Polynomials
- The Operator $\Psi$ for the Chromatic Number of a Graph
- Computing Semidefinite Programming Lower Bounds for the (Fractional) Chromatic Number Via Block-Diagonalization
- Some NP-complete problems in quadratic and nonlinear programming
- Approximate graph coloring by semidefinite programming
- A comparison of the Delsarte and Lovász bounds
- Cones of Matrices and Set-Functions and 0–1 Optimization
- On the Shannon capacity of a graph
- Copositive realxation for genera quadratic programming
- Coloring -colorable graphs using relatively small palettes
- Computing the Stability Number of a Graph Via Linear and Semidefinite Programming
- On copositive programming and standard quadratic optimization problems
This page was built for publication: Copositive programming motivated bounds on the stability and the chromatic numbers
