Max-Cut problem

3.1 Max-Cut problem

Given a graph G = (V,E) with edge weights w_ij for ij ∈ E and w_ij = 0 for ij ⁄∈ E, Max-Cut is the problem of finding a bipartition of the nodes V such that the sum of the weights of the edges across the bipartition is maximized. Let n = |V | be the cardinality of V ; we can state Max-Cut as

maximize	∑ _i<jw_ij
subject to	x ∈{-1,1}ⁿ.

We can rewrite the problem of Max-Cut as

maximize	x^TQx
subject to	x ∈{0,1}ⁿ.

where Q is the Laplacian matrix of the weighted graph G.

  3.1.1 Max-Cut heuristic
  3.1.2 Conversion tools
   subparagraphFrom Biq to BiqCrunch
   From Biq to BiqCrunch
   From Mac to BiqCrunch
   From Mac to BiqCrunch