Computing Semidefinite Programming Lower Bounds for the (Fractional) Chromatic Number Via Block-Diagonalization
From MaRDI portal
Publication:3629508
DOI10.1137/070683520zbMath1213.05081MaRDI QIDQ3629508
Nebojša Gvozdenović, Monique Laurent
Publication date: 27 May 2009
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/070683520
Terwilliger algebra; Hamming graph; semidefinite programming; chromatic number; Kneser graph; Lovász theta number
90C22: Semidefinite programming
90C27: Combinatorial optimization
05C15: Coloring of graphs and hypergraphs
Related Items
On the Generalized $\vartheta$-Number and Related Problems for Highly Symmetric Graphs, Partial Lasserre relaxation for sparse Max-Cut, New heuristics for the vertex coloring problem based on semidefinite programming, Think co(mpletely)positive! Matrix properties, examples and a clustered bibliography on copositive optimization, Copositive programming motivated bounds on the stability and the chromatic numbers, Block-diagonal semidefinite programming hierarchies for 0/1 programming, Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization, Symmetric sums of squares over \(k\)-subset hypercubes, Constraint selection in a build-up interior-point cutting-plane method for solving relaxations of the stable-set problem, Chromatic Gallai identities operating on Lovász number, Unnamed Item, The CP-Matrix Approximation Problem, Copositive Programming, Invariant Semidefinite Programs, Exact Solution of Graph Coloring Problems via Constraint Programming and Column Generation, Matrix Relaxations in Combinatorial Optimization
Uses Software
