Combinatorial Optimization

Networks and Matroids

Eugene Lawler

• Publisher: Dover Publications
• Year: 2012
• eBook ISBN: 9780486143668
• Topic: Mathematics
• Subtopic: Counting & Numeration
• Index: Mathematics

Perceptively written text examines optimization problems that can be formulated in terms of networks and algebraic structures called matroids. Chapters cover shortest paths, network flows, bipartite matching, nonbipartite matching, matroids and the greedy algorithm, matroid intersections, and the matroid parity problems. A suitable text or reference for courses in combinatorial computing and concrete computational complexity in departments of computer science and mathematics.

ONE

Introduction

1
What is Combinatorial Optimization?

Combinatorial analysis is the mathematical study of the arrangement, grouping, ordering, or selection of discrete objects, usually finite in number. Traditionally, combinatorialists have been concerned with questions of existence or of enumeration. That is, does a particular type of arrangement exist? Or, how many such arrangements are there?

Quite recently, a new line of combinatorial investigation has gained increasing importance. The question asked is not “Does the arrangement exist?” or “How many arrangements are there?”, but rather, “What is a best arrangement?” The existence of a particular type of arrangement is usually not in question, and the number of such possible arrangements is irrelevant. All that matters is finding an optimal arrangement, whether it be one in a hundred or one in an effectively infinite number of possibilities.

The new study of combinatorial optimization owes its existence to the advent of the modern digital computer. Most currently accepted methods of solution to combinatorial optimization problems would hardly have been taken seriously 25 years ago, for the simple reason that no one could have carried out the computations involved. Moreover, the existence of the digital computer has also created a multitude of technical problems of a combinatorial character. A large number of combinatorial optimization problems have been generated by research in computer design, the theory of computation, and by the application of computers to a myriad of numerical and nonnumerical problems which have required new methods, new approaches, and new mathematical insights.

2
Some Representative Optimization Problems

Perhaps the best way to convey the nature of combinatorial optimization problems is to give some specific examples. The first six problems listed below involve graphs. We assume that a connected undirected graph G is given, together with a nonnegative length for each arc (when applicable). If the reader is not already familiar with graphic terminology, he should consult Chapter 2.

ARC-COVERING PROBLEM

An arc (i, j) is said to “cover” nodes i and j. What is the smallest possible subset of arcs that can be chosen, such that each node of G is covered by at least one arc of the subset?

ARC-COLORING PROBLEM

It is desired to paint the arcs of G various colors, subject to the constraint that not all the arcs in any cycle are painted the same color. What is the smallest number of colors that will suffice?

MIN-CUT PROBLEM

It is desired to find a subset of arcs (a “cut”) such that when these arcs are removed from G, the graph becomes disconnected. For what subset of arcs is the sum of the arc lengths minimized?

SPANNING-TREE PROBLEM

It is desired to find a subset of arcs such that when these arcs are removed from G, the graph remains connected. For what subset of arcs is the sum of the arc lengths maximized? (The complementary set of arcs is a “minimal spanning tree.”)

SHORTEST PATH PROBLEM

What is the shortest path between two specified nodes of G?

CHINESE POSTMAN’S PROBLEM

It is desired to find a tour (a closed path) that passes through each arc in G at least once. What is the shortest such tour?

ASSIGNMENT PROBLEM

An n × n matrix W = (w_ij) is given. It is desired to find a subset of the elements in W, with exactly one element in each row and in each column. For what subset is the sum of the elements minimized?

MACHINE SEQUENCING PROBLEM

A number of jobs are to be processed by a machine. For each job a processing time and a deadline are specified. How should the jobs be sequenced, so that the number of late jobs is minimized?

A “TWENTY QUESTIONS” PROBLEM

Consider the following game, not unlike the parlor game of Twenty Questions. One player chooses a “target” object from a known set of n objects. The probability that he chooses object i is p_i. These probabilities are known to the second player, who is to identify the target object by formulating a series of questions of the form, “Is the target contained in subset S of the objects?”, for some specified S. Assuming the first player answers these “yes or no” questions truthfully, how can the second player minimize the mean number of questions he must ask?

“RESTRICTED” SATISFIABILITY PROBLEM

A Boolean expression is given, in conjunctive normal form (i.e., “product-of-sums” form), with at most two literals in each term (sum) of the expression. For what assignment of 0, 1 values to the variables does the expression take on a “maximum” value? (The expression is satisfiable if and only if there is an assignment for which the expression takes on the value 1.)

3
When is a Problem Solved?

Of the ten problems listed in the previous section, the first seven can be solved by algorithms described in this book and the last three by well-known algorithms referenced at the end of this chapter.

But what does it mean to “solve” one of these problems? After all, there are only a finite number of feasible solutions to each of these problems. In a graph with m arcs and n nodes there are no more than 2^m possible subsets that might be arc coverings, no more than m^m possible arc colorings, no more than 2^m possible cuts, no more than nⁿ⁻² possible spanning trees, no more than 2^m possible paths, and no more than (2m)! tours of the type required for the Chinese Postman’s Problem. There are no more than n! feasible solutions to the assignment problem, no more than n! feasible sequences for n jobs, no more than (n!)² solutions to the Twenty Questions problem, no more than 2ⁿ possible assignments of values to n Boolean variables in the satisfiability problem. In order to solve any one of these problems, why do we not just program a computer to make a list of all the possible solutions and pick out the best solution from the list?

As a matter of fact, there may still be a few (very pure) mathematicians who would maintain that the problems we have listed are actually nonproblems, devoid of any real mathematical content. They would say that whenever a problem requires the consideration of only a finite number of possibilities the problem is mathematically trivial.

This line of reasoning is hardly satisfying to one who is actually confronted with the necessity of finding an optimal solution to one of these problems. A naive, brute force approach simply will not work. Suppose that a computer can be programmed to examine feasible solutions at the rate of one each nanosecond, i.e., one billion solutions per second. Then if there are n! feasible solutions, the computer will complete its task, for n = 20 in about 800 years, for n = 21 in about 16,800 years, and so on. Clearly, the running time of such a computation is effectively infinite. A combinatorial problem is not “solved” if we cannot live long enough to see the answer!

The challenge of combinatorial optimization is to develop algorithms for which the number of elementary computational steps is acceptably small. If this challenge is not of interest to “mathematicians,” it most certainly is to computer scientists. Moreover, the challenge will be met only through study of the fundamental nature of combinatorial algorithms, and not by any conceivable advance in computer technology.

4
The Criterion of Polynomial Boundedness

Suppose an algorithm is proposed for a combinatorial optimization problem. How should we evaluate its effectiveness?

There is a very pragmatic (and realistic) point of view that can be taken. When the algorithm is implemented on a commercially available computer, it should require only a “reasonable” expenditure of computer time and data storage for any instance of the combinatorial problem which one might “reasonably” expect to solve. It is in exactly this sense that the simplex method of linear programming has been proved to be effective in solving hundreds of thousands, perhaps millions, of problems over a period of more than 20 years.

The “rule of reason” is an accepted principle of adjudication in the law. But more objective, precise standards should be possible in a mathematical and scientific discipline. One generally accepted standard in the realm of combinatorial optimization is that of “polynomial boundedness.” An algorithm is considered “good” if the required number of elementary computational steps is bounded by a polynomial in the size of the problem.

The previous statement should raise a number of questions in the reader’s mind. What is an elementary computational step? Does not that depend on the type of computer to be used? What is meant by the “size” of a problem? Might not there be more than one way to define size? And, most important, why is a polynomial bound considered to be important?

Consider first the significance of polynomial bounds. A polynomial function grows much less rapidly than an exponential function and an exponential function grows much less rapidly than a factorial function. Suppose one algorithm for solving the arc-covering problem requires 100 n³ steps, and another requires 2ⁿ steps, where n is the number of nodes. The exponential algorithm is more efficient for graphs with no more than 17 nodes. For larger graphs, however, the polynomial algorithm becomes increasingly better, with an exponentially growing ratio in running times. A 50-node problem may be quite feasible for the polynomial algorithm, but it is almost certain to be impossible for the exponential algorithm.

This is not to say that such comparisons may not be misleading. The crossover point may be well beyond the feasible range of either algorithm, in which case the exponential algorithm is certainly better in practice. Moreover, there are algorithms which are theoretically exponential, but behave like polynomial algorithms for all practical purposes. Prime examples are the simplex algorithms, which have empirically been observed to require an amount of computation that grows algebraically with the number of variables and the number of constraints of the linear programming problem. Yet it has been shown that for a properly contrived class of problems the simplex algorithms require an exponentially growing number of operations.

However, polynomial-bounded algorithms are, in fact, almost always “good” algorithms. The criterion of polynomial bou...

Table of contents

• Cover
• Title Page
• Copyright Page
• Preface
• Contents
• Chapter 1 Introduction
• Chapter 2 Mathematical Preliminaries
• Chapter 3 Shortest Paths
• Chapter 4 Network Flows
• Chapter 5 Bipartite Matching
• Chapter 6 Nonbipartite Matching
• Chapter 7 Matroids and the Greedy Algorithm
• Chapter 8 Matroid Intersections
• Chapter 9 The Matroid Parity Problem
• Author Index
• Subject Index