motzkin-straus formulation

Finite convergence of sum-of-squares hierarchies for the stability number of a graph

  • Monique Laurent
  • Luis Felipe Vargas
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming Tags , , , , , , , , ,

    We investigate a hierarchy of semidefinite bounds $\vartheta^{(r)}(G)$ for the stability number $\alpha(G)$ of a graph $G$, based on its copositive programming formulation and introduced by de Klerk and Pasechnik [SIAM J. Optim. 12 (2002), pp.875–892], who conjectured convergence to $\alpha(G)$ in $r=\alpha(G) -1$ steps. Even the weaker conjecture claiming finite convergence is still open. … Read more

    Continuous Cubic Formulations for Cluster Detection Problems in Networks

  • Vladimir Boginski
  • Austin Buchanan
  • Sergiy Butenko
  • Vladimir Stozhkov
    • Categories Combinatorial Optimization, Global Optimization, Integer Programming Tags , , , , , ,

    The celebrated Motzkin-Straus formulation for the maximum clique problem provides a nontrivial characterization of the clique number of a graph in terms of the maximum value of a nonconvex quadratic function over a standard simplex. It was originally developed as a way of proving Tur\'{a}n’s theorem in graph theory, but was later used to develop … Read more