ABSTRACT
Theoptimizationof a givenobjective,whileworkingwith limited resources is a fundamental problem that occurs in all walks of life, and is especially important in computer science and operations research. Problems in discrete optimization vary widely in their complexity, and efficient solutions are derived formany of these problems by studying their combinatorial structure and understanding their fundamental properties. In this chapter, we study several problems and advanced algorithmic techniques for solving them. One of the basic topics in this field is the study of network flow and related optimization problems; these problems occur in various disciplines, and provide a fundamental framework for solving problems. For example, the problem of efficiently moving entities, such as bits, people, or products, from one place to another in an underlying network, can
and
be modeled as a network flow problem. Network flow finds applications in many other areas such as matching, scheduling, and connectivity problems in networks. The problem plays a central role in the fields of operations research and computer science, and considerable emphasis has been placed on the design of efficient algorithms for solving it. The network flow problem is usually formulated on directed graphs (which are also known as
networks). A fundamental problem is themaximum flow problem, usually referred to as the maxflow problem. The input to this problem is a directed graph G = (V ,E), a nonnegative capacity function u : E → + that specifies the capacity of each arc, a source vertex s ∈ V , and a sink vertex t ∈ V . The problem captures the situation when a commodity is being produced at node s, and needs to be shipped to node t, through the network. The objective is to send as many units of flow as possible from s to t, while satisfying flow conservation constraints at all intermediate nodes and capacity constraints on the edges. The problem will be defined formally later. Many practical combinatorial problems such as the assignment problem, and the problem of
finding the susceptibility of networks to failures due to faulty links or nodes, are special instances of the max-flow problem. There are several variations and generalizations of the max-flow problem including the vertex capacitated max-flow problem, the minimum-cost max-flow problem, the minimum-cost circulation problem, and the multicommodity flow problem. Section 8.2 discusses the matching problem. The single commodity maximum flow problem
is introduced in Section 8.3. The minimum-cut problem is discussed in Section 8.4. Section 8.5 discusses the min-cost flow problem. The multicommodity flow problem is discussed in Section 8.6. Section 8.7 introduces the problem of computing optimal branchings. Section 8.8 discusses the problemof coloring the edges and vertices of a graph. Section 8.9 discusses approximation algorithms for NP-hard problems. At the end, references to current research in graph algorithms are provided.
Anentire book [23] has beendevoted to the studyof various aspects of thematchingproblem, ranging from necessary and sufficient conditions for the existence of perfect matchings to algorithms for solving the matching problem. Many of the basic algorithms studied in Chapter 7 play an important role in developing various implementations for network flow and matching algorithms. First the matching problem, which is a special case of the max-flow problem is introduced. Then
the assignment problem, a generalization of the matching problem, is studied. The maximum matching problem is discussed in detail only for bipartite graphs. The same
principles are used to design efficient algorithms to solve the matching problem in arbitrary graphs. The algorithms for general graphs are complex due to the presence of odd-length cycles called blossoms, and the reader is referred to [26,Chapter 10 of first edition], or [29,Chapter 9] for a detailed treatment of how blossoms are handled.
