Next: Independent Set Up: Simulated Annealing Previous: Traveling Salesman Problem

### Maximum Cut

For a weighted graph G, the maximum cut problem seeks to partition the vertices into sets and so as to maximize the weight (or number) of edges with one vertex in each set. When the graph specifies an electronic circuit, the maximum cut in the graph defines the largest amount of data communication that can take place in the circuit simultaneously. As discussed in catalog Section , maximum cut is an NP-complete version of graph partitioning.

How can we formulate maximum cut for simulated annealing? The solution space consists of all possible vertex partitions; we save a factor of two over all vertex subsets because we can assume that vertex is fixed to be on the left side of the partition. The subset of vertices accompanying it can be represented using a bit vector. The cost of a solution will be the sum of the weights cut in the current configuration. A natural transition mechanism is to select one vertex at random and move it across the partition by simply flipping the corresponding bit in the bit vector. The change in the cost function will be the weight of its old neighbors minus the weight of its new neighbors, so it can be computed in time proportional to the degree of the vertex.

This kind of simple, natural modeling is the right type of heuristic to seek in practice.

Algorithms
Mon Jun 2 23:33:50 EDT 1997