LP duality in infinite hypergraphs

DOI10.1016/0095-8956(90)90098-KMaRDI QIDQ803165zbMATH OpenFDO

Authors Ron Aharoni, Ran Ziv

Publication date 1990

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0095-8956(90)90098-K

zbMATH Keywords

complementary slackness conditions of linear programmingfractional coverfractional matchingGallai's theoremstrong duality property

Mathematics Subject Classification ID

Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Linear programming (90C05)

Review text

A hypergraph has the strong duality property if it has a fractional matching and a fractional cover satisfying the complementary slackness conditions of linear programming. The authors prove that all graphs satisfy the strong duality property; then, they consider the duality property for families of intervals on the real line and obtain an extension of Gallai's theorem.

Recommendations

• Fractional matchings and covers in infinite hypergraphs
• Optimal fractional matchings and covers in infinite hypergraphs: existence and duality
• Strong LP duality in weighted infinite bipartite graphs
• A note on the duality between matchings and vertex covers in balanced hypergraphs
• Solution of two fractional packing problems of Lovász. (Reprint)

Cites work

• 2-Matchings and 2-covers of hypergraphs
• A generalization of Tutte's 1-factor theorem to countable graphs
• Fractional matchings and covers in infinite hypergraphs
• Injective choice functions for countable families
• König's Duality Theorem for Infinite Bipartite Graphs
• Matchings in infinite graphs
• Maximal tight sets and the Edmonds-Gallai decomposition for matchings
• Menger's theorem for countable graphs

Cited in

(8)

• Optimal fractional matchings and covers in infinite hypergraphs: existence and duality
• Infinite matching theory
• Strong LP duality in weighted infinite bipartite graphs
• On packing and covering polyhedra in infinite dimensions
• Duality in Infinite Graphs
• A note on the minimum size of matching-saturated graphs
• The Lovász-Cherkassky theorem in infinite graphs
• Fractional covers and matchings in families of weighted \(d\)-intervals

This page was built for publication: LP duality in infinite hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q803165)