Semidefinite programming relaxations for graph coloring and maximal clique problems

DOI10.1007/S10107-006-0026-ZzbMath1278.90299OpenAlexW2144606698MaRDI QIDQ868457

Igor Dukanovic, Franz Rendl

Publication date: 5 March 2007

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-006-0026-z

zbMATH Keywords

chromatic numberclique numbercutting planesLovász theta number

Mathematics Subject Classification ID

Semidefinite programming (90C22) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (34)

Mathematical Programming Models and Exact Algorithms ⋮ Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank ⋮ Copositive programming motivated bounds on the stability and the chromatic numbers ⋮ Copositivity cuts for improving SDP bounds on the clique number ⋮ A boundary point method to solve semidefinite programs ⋮ An application of the Lovász-Schrijver \(M(K, K)\) operator to the stable set problem ⋮ Constraint selection in a build-up interior-point cutting-plane method for solving relaxations of the stable-set problem ⋮ New heuristics for the vertex coloring problem based on semidefinite programming ⋮ Optimizing over the Closure of Rank Inequalities with a Small Right-Hand Side for the Maximum Stable Set Problem via Bilevel Programming ⋮ The stable set problem: clique and nodal inequalities revisited ⋮ Strong lift-and-project cutting planes for the stable set problem ⋮ Ellipsoidal Relaxations of the Stable Set Problem: Theory and Algorithms ⋮ Binary Positive Semidefinite Matrices and Associated Integer Polytopes ⋮ On Integrality in Semidefinite Programming for Discrete Optimization ⋮ Calmness of partial perturbation to composite rank constraint systems and its applications ⋮ Chromatic Gallai identities operating on Lovász number ⋮ Binary positive semidefinite matrices and associated integer polytopes ⋮ A simple simulated annealing algorithm for the maximum clique problem ⋮ A branch and cut solver for the maximum stable set problem ⋮ A New Approach to the Stable Set Problem Based on Ellipsoids ⋮ A semidefinite programming-based heuristic for graph coloring ⋮ On the Lovász theta function and some variants ⋮ General cut-generating procedures for the stable set polytope ⋮ A linear complementarity based characterization of the weighted independence number and the independent domination number in graphs ⋮ A new lift-and-project operator ⋮ A tutorial on branch and cut algorithms for the maximum stable set problem ⋮ Unnamed Item ⋮ Foundations of Set-Semidefinite Optimization ⋮ Gap, cosum and product properties of the θ′ bound on the clique number ⋮ Projection Methods in Conic Optimization ⋮ On different versions of the exact subgraph hierarchy for the stable set problem ⋮ Simple ingredients leading to very efficient heuristics for the maximum clique problem ⋮ Matrix optimization over low-rank spectral sets: stationary points and local and global minimizers ⋮ Strengthening Chvátal-Gomory Cuts for the Stable Set Problem

Uses Software

• SDPLR
• COL

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Using tabu search techniques for graph coloring
• Copositive programming motivated bounds on the stability and the chromatic numbers
• A boundary point method to solve semidefinite programs
• Reduction of symmetric semidefinite programs using the regular \(\ast\)-representation
• Geometric algorithms and combinatorial optimization
• The sandwich theorem
• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• Strengthening the Lovász \(\theta(\overline G)\) bound for graph coloring
• Solving standard quadratic optimization problems via linear, semidefinite and copositive pro\-gramming
• Improved lower bound on the Shannon capacity of \(C_7\)
• Symmetry groups, semidefinite programs, and sums of squares
• On approximate graph colouring and MAX-\(k\)-CUT algorithms based on the \(\vartheta\)-function
• A semidefinite programming-based heuristic for graph coloring
• Solving Some Large Scale Semidefinite Programs via the Conjugate Residual Method
• New Code Upper Bounds From the Terwilliger Algebra and Semidefinite Programming
• Semidefinite Bounds for the Stability Number of a Graph via Sums of Squares of Polynomials
• 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
• Computational Experience with Stable Set Relaxations
• A Spectral Bundle Method for Semidefinite Programming
• Solving Large-Scale Sparse Semidefinite Programs for Combinatorial Optimization
• Solving Lift-and-Project Relaxations of Binary Integer Programs

This page was built for publication: Semidefinite programming relaxations for graph coloring and maximal clique problems