Connections in Combinatorial Optimization [Hardcover]

Connections in Combinatorial Optimization
by Andras Frank
Oxford University Press, Oxford, 2011.

(Disclaimer: I have read some parts of the book in detail, and have skimmed over other parts. Thus, this review is based on
incomplete information; but, if I wait till I have studied all of the book, then the review may be delayed for far too long.)

Combinatorial Optimization (CO) is a vibrant area within the mathematical sciences with close ties to areas such as
Algorithms, Computational Complexity, Graph Theory, Mathematical Programming, and Operations Research. CO is built on some simple and powerful ideas and the interactions between them.

The book has three parts. Part 1 of the book, Chapters 1-5, gives an
elegant introduction to the core of CO including connectivity, paths
and bipartite matchings, network flows, polyhedral combinatorics, and
matroid theory. This part is valuable for all teachers and students of
CO. The presentation focuses on the fundamentals and gives a concise,
elegant development of these core topics. The author uses his own
perspective, and this adds to the charm. To mention one item: a
theorem on orienting the edges of a graph to meet degree requirements
is proved via the push-relabel flow algorithm of Goldberg and Tarjan
(Theorem 2.3.5, pp.60-63).

Part 2, Chapters 6-11, covers algorithms for flows and cuts, the
structure and representation of cuts, the splitting-off operation,
orientation of graphs, packing and covering of trees and arborescences,
and connectivity augmentation.

Part 3, Chapters 12-17, covers submodular optimization and extensions,
including matroid optimization, generalized polymatroids, submodular
functions, and covering supermodular functions by digraphs.

The author is one of the world's leading researchers in CO, and one of his long-term goals is to bring the big theorems to the people.

Those wishing to know more about the book should read the preface (freely accessible at the website of the publisher: Oxford University Press); it has a comprehensive discussion of the contents and the aims of the author.

[...]

Every book in mathematics has to strike a balance between the aim of
communicating core ideas simply and directly, and the level of rigour.
The author has opted for a rigorous presentation. The advantage of
this is the precision and the ability to fully harness the power of
formalisms and abstractions. But this means that readers new to the area
have to invest some time to master the notation.

Here are a couple of comments for the author/publisher: Is it possible
for the publisher to make a free PDF copy of the book available for
downloading? This feature is being used by some recent books, e.g.,
Diestel's "Graph Theory", and Williamson and Shmoys' "The Design of
Approximation Algorithms". A shorter and simpler version of the book,
based on Chapters 1-5 and aimed at undergraduate students, could serve
as an attractive introduction to CO.

Summary:
This book gives an elegant and precise coverage of some important
topics of CO. The coverage in Chapters 1-5 (Part 1) could serve the
needs of an introductory graduate course. Besides presenting some of
the key methods in the area, the book develops and explains abstract
submodular results. Everyone who teaches courses in CO will benefit
from this book. Moreover, the book is valuable for researchers and
Ph.D. level students working in CO and in areas related to CO, such as
Approximation Algorithms, Algorithmic Game Theory and Mechanism Design,
Learning Theory, Mathematical Programming, and Operations Research.

It seems appropriate to conclude by recalling an incident from more
than 80 years ago, pertaining to the birth of the subject of
Connectivity. In the spring of 1930, the mathematician Karl Menger
visited Budapest, and met Denes Konig. Menger described to Konig his
n-arc theorem (similar to Theorem 2.5.8 in this book). Konig was
interested, but did not believe this. "This evening" he said to Menger
"I won't go to sleep before having constructed a counterexample." The
next day, Konig admitted that he had had a sleepless night. Later on,
Konig added this theorem to his book "Theorie der endlichen and
unendlichen Graphen" (1936), and it is now regarded as the key theorem
of Connectivity. (K.Menger, J. Graph Theory 5 (1981) 341-350, "On the
origin of the n-arc theorem.")

› Go to Amazon.com to see the review  4.0 out of 5 stars