Papadimitriou Christos H - Combinatorial Optimization: Alogrithms and Complexity

Combinatorial Optimization:
Algorithms and Complexity

CHRISTOS H. PAPADIMITRIOU

University of California-Berkeley

KENNETH STEIGLITZ

Princeton University

DOVER PUBLICATIONS, INC.

Mineola, New York

To the memory of our fathers
Harilaos Papadimitriou
Irving Steiglitz

Copyright

Copyright 1982, 1998 by Christos H. Papadimitriou and Kenneth Steiglitz.

All rights reserved under Pan American and International Copyright Conventions.

Bibliographical Note

This Dover edition, first published in 1998, is a corrected, unabridged republication of the work originally published in 1982 by Prentice-Hall, Inc., New Jersey. It contains a new preface by the authors written especially for this Dover edition.

Library of Congress Cataloging-in-Publication Data

Papadimitriou, Christos H.

Combinatorial optimization: algorithms and complexity / Christos H. Papadimitriou, Kenneth Steiglitz.

p.cm.

Originally published: Englewood Cliffs, NJ. : Prentice Hall,

1982. With new pref.

Includes bibliographical references and index.

ISBN 0-486-40258-4 (pbk.)

1. Mathematical optimization. 2. Combinatorial optimization.

3. Computational complexity. I. Steiglitz, Kenneth, 1939

II. Title.

QA402.5.P37 1998

519.3dc21

98-21476

CIP

Manufactured in the United States by Courier Corporation

40258409

www.doverpublications.com

Contents

Chapter 4 COMPUTATIONAL CONSIDERATIONS
FOR THE SIMPLEX ALGORITHM

Chapter 6 PRIMAL-DUAL ALGORITHMS FOR
MAX-FLOW AND SHORTEST PATH:
FORD-FULKERSON AND DIJKSTRA

Chapter 7 PRIMAL-DUAL ALGORITHMS
FOR MIN-COST FLOW

7.4 An Explicit Primal-Dual Algorithm for the Hitchcock
Problem Algorithm Alphabeta

Chapter 9 EFFICIENT ALGORITHMS
FOR THE MAX-FLOW PROBLEM

12.2 An O(|E|log|V|) Algorithm for the Minimum
Spanning Tree Problem

Chapter 14 A CUTTING-PLANE ALGORITHM
FOR INTEGER LINEAR PROGRAMS

16.2 Pseudo-Polynomial Algorithms and "Strong"
NP- Completeness

16.3 Special Cases and Generalizations of /VP-Complete
Problems

16.3.2 Easy Special Cases of NP-Complete
Problems

16.3.3 Hard Special Cases of NP-Complete
Problems

17.2 Approximation Algorithms for the Traveling Salesman
Problem

Chapter 18 BRANCH-AND-BOUND
AND DYNAMIC PROGRAMMING

19.4 Problem 3: Topology of Offshore Natural-Gas
Pipeline Systems

Preface to the Dover Edition

During the fifteen years since Combinatorial Optimization first appeared, its authors have often discussed the possibility of a second edition. In some sense a second edition seemed very appropriate, even called for: Many exciting new results had appeared that would merit inclusion, while not quite so many and so exciting that the basic premises, style, and approach of the book would need to be reworked.

The current republication of the book by Dover gives us an interesting opportunity to look critically at the book, and the field it recounts, fifteen years later. In retrospect, we are now happy with our decision (if you can call it that) not to proceed with a second edition. This was a book about two fields, at a moment when they had reached a degree of joint maturity and cross-fertilization that can inspire and justify a book; this feeling of novelty and timeliness would have been lost in a second edition. It is so much more appropriate (and, quite frankly, fun) to contemplate the interim developments from the armchair of a preface-writer.

To take the subjects of the book in order, the ellipsoid algorithm for linear programming (which had just made our publication deadline) did not have as much impact in practice as it did in theory, but the interior point algorithm developed in 1984 by Karmarkar has changed the practice of solving linear programs at least by providing simplex with the kind of competition that leads to faster implementations. As for simplex and its variants, there were some very interesting algorithms due to Megiddo and Tardos, and the polynomial average-case result by Borgwardt; however, the quest for a strongly polynomial algorithm for linear programming is still very much the major open problem in the field. The questions of integrality and total unimodularity are also much better understood now. All these important advances are covered in an excellent more recent book:

A.Schrijver,Theory of Linear and Integer Programming, New York: Wiley-Interscience, 1986.

There have been substantial improvements in the running times of virtually all network and graph optimization algorithms discussed in the book: Network flow, minimum cost flow, shortest path, minimum spanning tree, matching, etc. These improvements were occasionally precipitated by an ingenious new way of looking at the problem, but more often they were the result of the introduction of interesting new data structures, the innovative use of randomization, of scaling, of methods for dealing with density, and other algorithmic techniques. For a snapshot ca. 1993 see:

R. K. Ahuja, T. L.Magnanti, J. B. Orlin, Network Flows, Englewood Cliffs, N.J.: Prentice-Hall, 1993.

As for complexity, the central question of P vs. NP is now as unanswered as ever. If anything, a solution seems somehow farther away today than then, because many more avenues of attack have been explored by now with interesting but markedly inconclusive results. There has been progress and new insights in complexity, albeit in aspects such as space complexity, interaction, and randomization, that are not central to the book (but see the next paragraph regarding the complexity of approximation). Parallel algorithms and complexity came and went. For a recent book on the subject see:

C. H. Papadimitriou, Computational Complexity, Reading, Mass.: Addison-Wesley, 1994.

Two of the last topics of the book, approximation algorithms and local search, have since exploded into two very active fields. The more impressive theoretical advances were made in approximationwe even have now an approximation scheme for the Euclidean traveling salesman problem. Many of these exciting approximation algorithms were in fact based on mathematical programming concepts and methods (primal dual, fixed-dimension integer programming, semi-definite programming). On the other hand, a sequence of unexpected results in complexity culminated in a proof, in 1992, that several of these problems cannot have a polynomial approximation scheme, unless of course P = NP. For a compilation of surveys of these topics see:

D. Hochbaum (ed.), Approximation Algorithms for NP-hard problems, Boston, Mass.: PWS Publishing, 1996.

Finally, in the past fifteen years we have seen the development of many families of heuristics for optimization problems, typically inspired by metaphors from physics or biology (and sometimes referred to collectively as new age algorithms), which can be considered as clever variants of local search: Simulated annealing, tabu search, genetic algorithms, Boltzmann machines, neural networks, and so on. For a review of some of these approaches, see: