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
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
