Max-Cut

Problem Description

The max-cut problem in a graph can be formulated as follows. Given a weighted graph G(V,E) with node set V = {1,...,n} and edge set E, partition the nodes of the graph into two subsets V1 and V2 such that the sum of the weights (costs) of the edges going from one subset to the other is maximized. We assume the costs are nonnegative (possibly 0). The problem is determined by the cost matrix C, where C(i,j) = C(j,i) is the cost (weight) of link (i,j).

Programs

maxcut1xa.m

scut.m