# A max-cut formulation of 0/1 programs

arXiv: https://arxiv.org/abs/1505.06840 · HTML: https://mlsanity.com/paper/1505.06840/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 May 2015.

## Built on by (most cited first, 1 of 1)

- [Efficient semidefinite bounds for multi-label discrete graphical models](https://mlsanity.com/paper/2111.12491/) (2021)

## Abstract (arXiv)

We show that the linear or quadratic 0/1 program[P:quadmin cTx+xTFx : :A,x =b;:x∈0,1n,]can be formulated as a MAX-CUT problem whose associated graph is simply related to the matrices F and ATA.Hence the whole arsenal of approximation techniques for MAX-CUT can be applied. We also compare the lower boundof the resulting semidefinite (or Shor) relaxation with that of the standard LP-relaxation and the first semidefinite relaxationsassociated with the Lasserre hierarchy and the copositive formulations of P.