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 starting with θ_ 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 θ_.
Copositive cuts for improving SDP bounds on the clique number / I. M., Bomze; F., Frommlet; Locatelli, Marco. - In: MATHEMATICAL PROGRAMMING. - ISSN 0025-5610. - 124:(2010), pp. 13-32. [10.1007/s10107-010-0363-9]
Copositive cuts for improving SDP bounds on the clique number
LOCATELLI, Marco
2010-01-01
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 starting with θ_ 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 θ_.File | Dimensione | Formato | |
---|---|---|---|
MathSciNet2679980.pdf
non disponibili
Tipologia:
Abstract
Licenza:
Creative commons
Dimensione
40.57 kB
Formato
Adobe PDF
|
40.57 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
MP_copositive_cuts.pdf
non disponibili
Tipologia:
Documento in Post-print
Licenza:
Creative commons
Dimensione
320.22 kB
Formato
Adobe PDF
|
320.22 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.