Combinatorial optimization. Polyhedra and efficiency (3 volumes) (Q1854113): Difference between revisions

Schrijver's 3 volumes on combinatorial optimization reflect the current state of the art in this field, in particular from the viewpoint of polyhedral combinatorics and efficient algorithms. Less emphasis is put on advanced data structures, approximative, randomized and parallel algorithms, semidefinite programming and graph decomposition. The book offers a masterly introduction with many interesting historical remarks as well as an in-depth survey of combinatorial optimization. It is divided into eight main parts with 83 chapters. The main parts are (I) paths and flows, (II) bipartite matching and covering, (III) nonbipartite matching and covering, (IV) matroids and submodular functions, (V) trees, branchings and connectors, (VI) cliques, stable sets and colouring, (VII) multiflows and disjoint paths and, finally, (VIII) hypergraphs. Volume A contains an introduction, preliminaries and the first three main parts. Volume B contains the main parts (IV)-(VI), and Volume C contains the last two parts, a survey of open problems, over 4500 references for further research and name and subject indices. The reader is supposed to have a basic knowledge of graph theory and linear as well as integer programming. The author gives short and elegants proof to all main results. In order to keep the overall size of the volumes under control, the topics applications and modelling of optimization problems, and computational methods for NP-hard problems are not treated. The first part of the book, devoted to paths and flows, starts with a description of various shortest paths methods. Thereafter it discusses disjoint paths giving several proofs for Menger's theorem, and continues with maximum flows, circulations and transshipments. Furthermore, the following topics are treated: path and flow polyhedra and total unimodularity, Dilworth's theorem and connectivity algorithms, in particular the Gomory-Hu tree. The second part starts with bipartite matchings (giving several proofs of Königs and Frobenius' theorems). Then the linear assignment problem is discussed with many historical remarks. The bipartite matching polytope, bipartite edge cover and stable sets, bipartite edge-colouring and transversals are further topics of part (II). A particular emphasis is put on \(b\)-matching and transportation problems with interesting information about early investigations in the former Soviet Union. The third part is devoted to nonbipartite matching and covering and discusses in detail the pioneering work of Tutte and Edmonds. The first chapter in this part is devoted to non-bipartite cardinality matching, again with detailed historical remarks. Then the matching polytope is studied and algorithms for the weighted nonbipartite matching problem are treated. Further chapters deal with edge-colourings (Vizing's theorem), the Chinese postman problem, \(T\)-cuts and \(T\)-joins, \(2\)-matching, \(2\)-cover and \(2\)-factor problems, \(b\)-matchings, bidirected graphs, the perfect matching polytope and the perfect matching lattice. Volume B starts with matroids. Again detailed historical remarks are given which demonstrate the development of this notion. The chapter finds its classical continuation with the greedy algorithm and the independent set polytope. The next chapters treat matroid intersection problems and algorithms, matroid union and matroid matching. Then submodular functions and polymatroids are introduced and a strongly polynomial-time algorithm for finding the minimum of a submodular function is described. Finally, the author deals with polymatroid intersection, Dilworth truncation and closes this part with generalizations of submodular functions based on lattice families, intersecting families and crossing families. Part (V) is devoted to trees, branchings and connectors. It starts with a chapter on shortest spanning trees and the corresponding historic background. Then the packing and covering of trees is treated. Moreover, trees in directed graphs are considered, namely branchings and arborescences. Further chapters deal with biconnectors and bibranchings, minimum directed cut covers and the packing of directed cuts as well as with strong connectors. Chapter 58 describes the basics of the travelling salesman problem together with extensive historical notes and a detailed list of further references. Finally, matching forests and submodular functions on directed graphs are investigated. Further chapters deal with graph orientation problems, network synthesis and connectivity augmentation. Part (VI) is devoted to problems which are NP-hard in general,namely cliques, stable sets and colourings. In the case of perfect graphs these problems become polynomially solvable. Therefore perfect graphs are treated in detail and many interesting historical remarks are provided. Moreover, it is shown that a maximum-weighted stable set and a minimum weight clique cover in a perfect graph can even be found in strongly polynomial time. Finally, \(T\)-perfect graphs and claw-free graphs are considered. Volume C starts with part (VII) on multicommodity flows and disjoint paths. After discussing the basic properties, the two commodity case is treated. Then it is investigated to which extent Hu's theorem can be generalized to three or more commodities. In the next chapter the \(T\)-path problem and Mader's theorem is analyzed. This problem becomes particularly interesting in planar graphs which are treated in Chapter 74. In particular, Okamura's theorem is proved. Further chapters deal with cuts, odd circuits and multicommodity flows and graphs on surfaces where an interesting homotopic circulation theorem is proved. The last part of this compendium is devoted to hypergraphs and their relation to matching, vertex cover, edge cover and the stable set problem. Starting from packing and blocking problems in hypergraphs, the author describes ideal, Mengerian and binary hypergraphs and gives the short proof of Guenin for Seymour's characterization of binary Mengerian hypergraphs. Then a survey on relations between matroids and multicommodity flows in hypergraphs is given. Moreover, stable sets and edge covers in hypergraphs are studied. Finally, balanced and unimodular hypergraphs are introduced and studied. These three volumes contain an immense richness of results up to 2002 and will prove to be indispensible for any further research in the field of combinatorial optimization.