A MAX-CUT FORMULATION OF 0/1 PROGRAMS

Jean-Bernard Lasserre 1
1 LAAS-MAC - Équipe Méthodes et Algorithmes en Commande
LAAS - Laboratoire d'analyse et d'architecture des systèmes
Abstract : We show that the linear or quadratic 0/1 program \[P:\quad\min\{ c^Tx+x^TFx : \:A\,x =b;\:x\in\{0,1\}^n\},\] can be formulated as a MAX-CUT problem whose associated graph is simply related to the matrices $\F$ and $\A^T\A$. Hence the whole arsenal of approximation techniques for MAX-CUT can be applied. We also compare the lower bound of the resulting semidefinite (or Shor) relaxation with that of the standard LP-relaxation and the first semidefinite relaxations associated with the Lasserre hierarchy and the copositive formulations of $P$.
Document type :
Journal articles
Complete list of metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-01154698
Contributor : Jean Bernard Lasserre <>
Submitted on : Tuesday, December 22, 2015 - 2:31:37 PM
Last modification on : Friday, January 10, 2020 - 9:10:08 PM
Long-term archiving on: Wednesday, March 23, 2016 - 2:09:38 PM

Files

maxcut-R3.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01154698, version 3
  • ARXIV : 1505.06840

Citation

Jean-Bernard Lasserre. A MAX-CUT FORMULATION OF 0/1 PROGRAMS. Operations Research Letters, Elsevier, 2016, 44 (2), pp.158--164. ⟨hal-01154698v3⟩

Share

Metrics

Record views

246

Files downloads

134