The first cut is the cheapest: improving SDP bounds for the clique number via copositivity

Immanuel M. Bomze (immanuel.bomzeunivie.ac.at)
Florian Frommlet (florian.frommletunivie.ac.at)
Marco Locatelli (locatellidi.unito.it)

Abstract: In this paper we propose to improve the well known Lovász-Schrijver bound for the Maximum Clique Problem by adding linear cuts based on copositive matrices. Candidates for these matrices are obtained from graphs which have a clique number relatively easy to compute, e.g., triangle-free and K4-free graphs or compositions (cosums) of such graphs. In the literature there exist different hierarchies of bounds which start with the Lovász-Schrijver bound. Dominance results of the higher-order bounds in these hierarchies with respect to the bounds proposed in this paper are proved. On the other hand, the cost of the bounds in the hierarchies rapidly increases with the order, while the cost of the bounds proposed here is comparable with that for the computation of the Lovász-Schrijver bound itself.

Keywords: Lovász-Schrijver bound, clique number, linear cuts, semidefinite programming

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Combinatorial Optimization (Graphs and Matroids )

Citation:

Download: [PDF]

Entry Submitted: 08/10/2006
Entry Accepted: 08/10/2006
Entry Last Modified: 04/25/2007

Modify/Update this entry