Integral infeasibility and testing total dual integrality

DOI10.1016/0167-6377(91)90084-3MaRDI QIDQ757248zbMATH OpenOpenAlexFDO

Authors David Applegate, William Cook, S. Thomas McCormick

Publication date 1991

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-6377(91)90084-3

zbMATH Keywords

linear systempolyhedratotal dual integralityfeedback sets in directed graphs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Integer programming (90C10) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Linear systems in control theory (93C05)

Recommendations

• Alternatives for testing total dual integrality
• A polynomial-time test for total dual integrality in fixed dimension
• Intractability results for integration and discrepancy
• Characterizations of Total Dual Integrality
• scientific article; zbMATH DE number 3885657
• Total dual integrality of the linear complementarity problem
• Total dual integrality and integral solutions of the linear complementarity problem
• An intractability result for multiple integration
• On Testing Integrability
• On totally dual integral systems

Cites work

• scientific article; zbMATH DE number 3888925 (Why is no real title available?)
• scientific article; zbMATH DE number 3156381 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3580570 (Why is no real title available?)
• A Minimax Theorem for Directed Graphs
• A generalization of max flow—min cut
• A polynomial-time test for total dual integrality in fixed dimension
• Finding feasible vectors of Edmonds-Giles polyhedra
• Integer Programming with a Fixed Number of Variables
• Matching theory
• Polynomial Algorithms for Totally Dual Integral Systems and Extensions
• Total dual integrality and integer polyhedra
• Total weak unimodularity: Testing and applications

Cited in

(7)

• Ranking tournaments with no errors. II: Minimax relation
• Ranking tournaments with no errors. I: Structural description
• A primal-dual algorithm for weighted abstract cut packing
• Counting as integration in feasible analysis
• A polynomial-time test for total dual integrality in fixed dimension
• On the integral dicycle packings and covers and the linear ordering polytope
• Alternatives for testing total dual integrality

This page was built for publication: Integral infeasibility and testing total dual integrality

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