Combinatorial Optimization¶
Schrijver, A. (2003). Combinatorial Optimization: Polyhedra and Efficiency. Springer.
Cited by¶
3 citations across 3 artifacts.
Each citation links to the sentence it supports in the citing article.
Primes¶
- Network Flow Models
- The totally-unimodular structure of network-flow constraint matrices guarantees integer optimal solutions without explicit integer-programming treatment, making network-flow formulations distinctly more tractable than general ILPs, a property Schrijver (2003) develops within the broader theory of totally unimodular matrices and integer polyhedra.
This sourceComprehensive treatment of network flow within combinatorial optimization, including totally-unimodular structure and polynomial-time algorithms.
- The totally-unimodular structure of network-flow constraint matrices guarantees integer optimal solutions without explicit integer-programming treatment, making network-flow formulations distinctly more tractable than general ILPs, a property Schrijver (2003) develops within the broader theory of totally unimodular matrices and integer polyhedra.
Domain-specific¶
- Goldberg–Seymour Theorem
- Matching
- The matching polytope — the convex hull of characteristic vectors of matchings in \(G\) — has a complete linear-programming description for bipartite graphs (nonnegativity per edge plus the degree constraints per vertex), and that description is integral, the bipartite incidence matrix being totally unimodular; for general graphs those same constraints define only a fractional relaxation whose vertices are half-integral, and the exact description additionally requires Edmonds's odd-set inequalities, placing matching at the center of the polyhedral combinatorics literature
This sourceThe standard reference for the polyhedral picture this sentence states: the bipartite matching polytope described exactly by nonnegativity and the degree constraints and integral there by total unimodularity, the same constraints yielding only a half-integral relaxation in a general graph, and Edmonds's odd-set inequalities as the additional family the exact description requires.
- The matching polytope — the convex hull of characteristic vectors of matchings in \(G\) — has a complete linear-programming description for bipartite graphs (nonnegativity per edge plus the degree constraints per vertex), and that description is integral, the bipartite incidence matrix being totally unimodular; for general graphs those same constraints define only a fractional relaxation whose vertices are half-integral, and the exact description additionally requires Edmonds's odd-set inequalities, placing matching at the center of the polyhedral combinatorics literature
Verification¶
This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.
Registry ID ref:4ddd987d042e · see in the full table