Preface

Summary

This is the house that Jack built. Ralph prepared the lot. There were many independent contractors who did beautiful work; some putting on splendid additions. Martin, Laci, and Lex rewired the place. The work continues. But this is the house that Jack built.

This textbook is designed to serve as lecture notes for a one-semester course focusing on combinatorial optimization. I am primarily targeting this at the graduate level, but much of the material may also be suitable for excellent undergraduate students. The goal is to provide an enticing, rigorous introduction to the mathematics of the subject, within the context of a one-semester course. There is a strong emphasis on the unifying roles of matroids, submodularity, and polyhedral combinatorics.

I do not pretend that this book is an exhaustive treatment of combinatorial optimization. I do not emphasize data structures, implementation details, or sophisticated approaches that may yield decidedly faster and more practical algorithms. Such are important issues, but I leave them for later independent study. The approach that I take is to focus, mostly, on the beautiful. Also, I note that the terrain of the field shifts rapidly. For example, Gomory's seminal work on integer programming from the 1960s, which was featured prominently in textbooks in the early 1970s, was out of vogue by the late 1970s and through the early 1990s when it was assessed to have no practical value.