next up previous contents index CD CD Algorithms
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 tex2html_wrap_inline25869 and tex2html_wrap_inline25871 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 gif, 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 tex2html_wrap_inline25873 possible vertex partitions; we save a factor of two over all vertex subsets because we can assume that vertex tex2html_wrap_inline25875 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.

Mon Jun 2 23:33:50 EDT 1997