Immanuel
Bomze
Title:
The first cut is the cheapest-improving SDP bounds for the
clique number
Abstract:
This is joint work with F. Frommlet and M. Locatelli
We present
an improvement of the Lovasz - Schrijver bound for the clique number by
adding linear cuts. Based on the Motzkin/Straus quadratic formulation
of the maximum clique problem we obtain valid cuts by considering
subgraphs of the original graph with known clique number. We develop
simple heuristic algorithms to find suitable subgraphs and study
several classes of graphs for which we can actually obtain an
improvement of the Schrijver bound, among them circulant graphs. The
talk also addresses the use of several products and cosums of graphs
for constructing hard instances.