clique number

Quadratic factorization heuristics for copositive programming

  • Immanuel M. Bomze
  • Florian Jarre
  • Franz Rendl
    • Categories (Mixed) Integer Linear Programming, Global Optimization, Linear, Cone and Semidefinite Programming Tags , ,

    Copositive optimization problems are particular conic programs: extremize linear forms over the copositive cone subject to linear constraints. Every quadratic program with linear constraints can be formulated as a copositive program, even if some of the variables are binary. So this is an NP-hard problem class. While most methods try to approximate the copositive cone … Read more

    Semidefinite programming relaxations for graph coloring and maximal clique problems

  • Igor Dukanovic
  • Franz Rendl
    • Categories Combinatorial Optimization, Graphs and Matroids Tags , , ,

    The semidefinite programming formulation of the Lovasz theta number does not only give one of the best polynomial simultaneous bounds on the chromatic number and the clique number of a graph, but also leads to heuristics for graph coloring and extracting large cliques. This semidefinite programming formulation can be tightened toward either number by adding … Read more