Copositivity cuts for improving SDP bounds on the clique number

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

Abstract: Adding cuts based on copositive matrices, we propose to improve Lovász' bound on the clique number and its tightening introduced by McEliece, Rodemich, Rumsey, and Schrijver. Candidates for cheap and efficient copositivity cuts of this type are obtained from graphs with known clique number. The cost of previously established semidefinite programming bound hierarchies rapidly increases with the order (and quality requirements). By contrast, the bounds proposed here are relatively cheap in the sense that computational effort is comparable to that required for tightening introduced by McEliece, Rodemich, Rumsey, and Schrijver.

Keywords: Lovász bound, maximum clique problem, stability number, semidefinite programming

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

Category 2: Combinatorial Optimization (Graphs and Matroids )

Citation: Technical report TR-ISDS 2007-05, University of Vienna. To appear in: Mathematical Programming B (2012).

Download: [PDF]

Entry Submitted: 08/10/2006
Entry Accepted: 08/10/2006
Entry Last Modified: 03/11/2010

Modify/Update this entry