  


Computing semidefinite programming lower bounds for the (fractional) chromatic number via blockdiagonalization
Nebojsa Gvozdenovic (nebojsacwi.nl) Abstract: Recently we investigated in "The operator $\Psi$ for the Chromatic Number of a Graph" hierarchies of semidefinite approximations for the chromatic number $\chi(G)$ of a graph $G$. In particular, we introduced two hierarchies of lower bounds, the `$\psi$'hierarchy converging to the fractional chromatic number, and the `$\Psi$'hierarchy converging to the chromatic number of a graph. In both hierarchies the first order bounds are related to the Lov\' asz theta number, while the second order bounds would already be too costly to compute for large graphs. As an alternative, relaxations of the second order bounds are proposed. We present here our experimental results with these relaxed bounds for Hamming graphs, Kneser graphs and DIMACS benchmark graphs. Symmetry reduction plays a crucial role as it permits to compute the bounds using more compact semidefinite programs. In particular, for Hamming and Kneser graphs, we use the explicit blockdiagonalization of the Terwilliger algebra given by Schrijver. Our numerical results indicate that the new bounds can be much stronger than the Lov\' asz theta number. For some of the DIMACS instances we improve the best known lower bounds significantly. Keywords: Chromatic number, Lov\' asz theta number, semidefinite programming, Terwilliger algebra, Hamming graph, Kneser graph Category 1: Combinatorial Optimization Category 2: Linear, Cone and Semidefinite Programming Citation: This is a follow up paper of "The operator $\Psi$ for the Chromatic Number of a Graph" Download: [PDF] Entry Submitted: 02/24/2007 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  