Combinatorial optimization. Polyhedra and efficiency (3 volumes)
Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Combinatorial aspects of matroids and geometric lattices (05B35) Hypergraphs (05C65) Computational aspects related to convexity (52B55) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)
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.
- Combinatorial optimization -- polyhedra and efficiency: a book review
- Combinatorial Optimization. Polyhedra and efficiency. CD-ROM
- Polyhedral techniques in combinatorial optimization I: Theory
- Polyhedral Combinatorics in Combinatorial Optimization
- Polyhedral combinatorics and combinatorial optimization
- Polyhedral techniques in combinatorial optimization II: applications and computations
- scientific article; zbMATH DE number 5764441
- scientific article; zbMATH DE number 702975
- scientific article; zbMATH DE number 1297592
- Block-diagonal semidefinite programming hierarchies for 0/1 programming
- On a theorem of Sewell and Trotter
- Integer version of the multipath flow network synthesis problem
- The box-TDI system associated with 2-edge connected spanning subgraphs
- Better bounds for minimizing SONET ADMs
- The subdivision-constrained minimum spanning tree problem
- Minimizing the stabbing number of matchings, trees, and triangulations
- Minimum mean cycle problem in bidirected and skew-symmetric graphs
- Weighted restricted 2-matching
- Pure Nash equilibria in player-specific and weighted congestion games
- Packing trees with constraints on the leaf degree
- Set covering and packing formulations of graph coloring: Algorithms and first polyhedral results
- Computing monotone disjoint paths on polytopes
- A geometric characterization of ``optimality-equivalent relaxations
- A faster strongly polynomial time algorithm for submodular function minimization
- Multiline addressing by network flow
- On Kalai's conjectures concerning centrally symmetric polytopes
- On minimum \(k\)-modal partitions of permutations
- The \(S\)-digraph optimization problem and the greedy algorithm
- Statistics to measure correlation for data mining applications
- Greedily constructing maximal partial f-factors
- Rooted \(k\)-connections in digraphs
- Minimum-weight cycle covers and their approximability
- Approximation algorithms for the weighted independent set problem in sparse graphs
- Constrained inverse min-max spanning tree problems under the weighted Hamming distance
- Weighted sum coloring in batch scheduling of conflicting jobs
- Approximating the maximum internal spanning tree problem
- A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids
- Covering skew-supermodular functions by hypergraphs of minimum total size
- Optimizing the marriage market: an application of the linear assignment model
- Some classical combinatorial problems on circulant and claw-free graphs: The isomorphism and coloring problems on circulant graphs and the stable set problem on claw-free graphs
- Flows with unit path capacities and related packing and covering problems
- Ehrhart polynomials of matroid polytopes and polymatroids
- Stable sets, corner polyhedra and the Chvàtal closure
- Approximating the maximum 3-edge-colorable subgraph problem
- Tight spans of distances and the dual fractionality of undirected multiflow problems
- A note on submodular set cover on matroids
- Homomorphisms of triangle-free graphs without a \(K_{5}\)-minor
- Odd-\(K_{4}\)'s in stability critical graphs
- Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid
- Polyhedral proof methods in combinatorial optimization
- On return path packing.
- A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem.
- More complete intersection theorems
- Uniqueness of equilibria in atomic splittable polymatroid congestion games
- The weakly connected independent set polytope in corona and join of graphs
- On the m-clique free interval subgraphs polytope: polyhedral analysis and applications
- Constant factor approximation for the weighted partial degree bounded edge packing problem
- The mixed evacuation problem
- Algorithms for detecting dependencies and rigid subsystems for CAD
- Schubert polynomials as integer point transforms of generalized permutahedra
- Approximation algorithms for constructing specific subgraphs with minimum number of length-bounded stock pieces
- Linkage on the infinite grid
- Belief propagation for the maximum-weight independent set and minimum spanning tree problems
- Matroid optimisation problems with nested non-linear monomials in the objective function
- Costly circuits, submodular schedules and approximate Carathéodory theorems
- On the approximability of the maximum interval constrained coloring problem
- Discrete convexity in joint winner property
- Fast integer-valued algorithms for optimal allocations under constraints in stratified sampling
- Rainbow spanning trees in properly coloured complete graphs
- On the Langberg-Médard multiple unicast conjecture
- Algebraic matroids and Frobenius flocks
- On box-perfect graphs
- Gross substitutability: an algorithmic survey
- Domination parameters with number 2: interrelations and algorithmic consequences
- On imposing connectivity constraints in integer programs
- Approximation algorithms for constructing spanning \(K\)-trees using stock pieces of bounded length
- A note on counting independent terms in asymptotic expressions of computational complexity
- On the information ratio of non-perfect secret sharing schemes
- Core index of perfect matching polytope for a 2-connected cubic graph
- Coordination mechanisms for scheduling games with proportional deterioration
- The search value of a set
- Colored spanning graphs for set visualization
- Chain-constrained spanning trees
- On vertex-parity edge-colorings
- Improved bounds for randomized preemptive online matching
- Lexicographical polytopes
- Minimal arc-sets spanning dicycles
- The complexity of the Clar number problem and an exact algorithm
- Graphs vertex-partitionable into strong cliques
- A logarithmic approximation for polymatroid congestion games
- Refuting a conjecture of goemans on bounded degree spanning trees
- Polyhedra and parameter spaces for matroids over valuation rings
- Efficient algorithms for computing the inner edit distance of a regular language via transducers
- Convex equipartitions of colored point sets
- Complexity of strict robust integer minimum cost flow problems: an overview and further results
- The multi-terminal vertex separator problem: polyhedral analysis and branch-and-cut
- Antimatroids induced by matchings
- Computing solutions of the multiclass network equilibrium problem with affine cost functions
- Graph edge coloring: a survey
- Rectangle blanket problem: binary integer linear programming formulation and solution algorithms
- Matroid prophet inequalities and applications to multi-dimensional mechanism design
- Top-\(k\) overlapping densest subgraphs
- A stronger multiple exchange property for \(\mathrm{M}^{\natural }\)-concave functions
- On the intersection of infinite matroids
- A tropical isoperimetric inequality
- A convolution formula for Tutte polynomials of arithmetic matroids and other combinatorial structures
- On matrices with the Edmonds-Johnson property arising from bidirected graphs
- A simple proof characterizing interval orders with interval lengths between 1 and \(k\)
- Two new reformulation convexification based hierarchies for 0-1 MIPs
This page was built for publication: Combinatorial optimization. Polyhedra and efficiency (3 volumes)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1854113)
