The Minimum/Maximum Cut Problem |
Many optimization problems can be formulated in terms of finding that minimum (or maximum) cut in a network or graph. A cut is formed by partitioning the nodes of a graph into two mutually exclusive sets. An edge between a node in one set and a node in the other is said to be in the cut. The weight, or the capacity, of the cut is the sum of the weights of the edges that have exactly one endpoint in each of the two sets.
The problem of finding the minimum weight cut in a graph plays an important role in the design of communication networks. If a few of the links are cut or otherwise fail, the network may still be able to transmit messages between any pair of its nodes. If enough links fail, however, there will be at least one pair of nodes that cannot communicate with each other. Thus an important measure of the reliability of a network is the minimum number of links that must fail in order for this to happen. This number is referred to as the edge connectivity of the network and can be found by assigning a weight of 1 to each link and finding a minimum weight cut. In other applications, such as the open pit mining problem, we seek a minimum weight cut such that a specific pair of nodes, say node s and node t, are not in the same set. Solving this type of problem, known as a minimum s-t cut problem, is a fundamental part of the calculations used to find the baseball elimination and clinch numbers. Ahuja, Magnanti and Orlin [AMO93], present many other applications of cut problems.
The problem of cluster analysis, partitioning a set of data points into groups of "closely related" observations, can be modeled as a maximum cut problem. The points in a particular group, or cluster, should be more "similar" or "close" to each other than they are to points in other clusters. Cluster analysis can be formulated as a maximum cut problem by creating a graph that contains a node for each data point and an edge between each pair of points. The weight of the edge is determined by the relative "closeness" of the points represented by the nodes it connects. For numerical data, for example, the relative closeness may be defined as the Euclidean distance. The clusters that are formed by finding maximum weight cuts in this graph have the property that points in one cluster are more dissimilar from points in other clusters. Barahona, Grötschel, Jünger and Reinelt [BGJR88] describe how the maximum cut problems also arises in the design of VLSI circuits and the analysis of spin-glass models.
Rather than using enumeration to find the maximum weight cut, RIOT uses a "greedy" approximation algorithm due to Sahni and Gonzales [SG76] which is very fast and always finds a cut that has at least half the weight of the true maximum cut. For example, if you use the application to create a graph which has a maximum cut of weight 150, then RIOT will find a cut with weight 75 or higher. This type of procedure is known as an approximation algorithm since it does not always find the optimal solution, but it gives a guarantee about the quality of the solutions that it does find. In the future, RIOT will also provide an implementation of a maximum cut algorithm due to Goemans and Williamson [GW94] which finds a cut with weight at least 88% of optimal. A comprehensive treatment of approximation algorithms for a wide variety of problems can be found in "Approximation Algorithms for NP-Hard Problems", [H96] edited by Dorit S. Hochbaum.
Note that for the maximum cut, RIOT may not give you an optimal solution. See if you can find a better solution than the cut produced by the "greedy" algorithm.
Click here to TRY IT!
[BGJR88] F. Barahona, M. Grötschel, M. Jünger and G. Reinelt, "An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design," Operations Research, 3:493-513 (1988)
[GW94] M. Goemans and P. Williamson, "Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming," J. Assoc. Comput. Mach., (1994).
[H96] Dorit S. Hochbaum, editor. "Approximation Algorithms for NP-Hard Problems," PWS Publishing Company, Boston, MA. 1996
[SG76] S. Sahni and T. Gonzales, "P-complete approximation problems," Journal of the ACM 23:555-565. 1976