Selected Applications of Minimum Cuts in Networks

This paper provides a review and a synthesis of applications of minimum cuts to a variety of combinatorial optimization problems, including linear and non-linear integer programming, problems in location theory, graph theory, sequencing and scheduling, and other areas. The central theme is a binary quadratic programming formulation of the minimum cut problem. After reviewing alternative formulations, extensions, and direct applications ofminimum cuts in network problems, the problem of finding a closure with maximum weight ina directed graph is considered. This problem can be solved as a minimum cut problem, which allows other related problems to be solved as a sequence of minimum cut problems. The paper concludes by exploring more difficult versions of the minimum cut problem involving negative capacities or additional constraints.