On the complexity of recognizing integrality and total dual integrality of the \(\{0,1/2\}\)-closure

DOI10.1016/j.orl.2021.11.009OpenAlexW3216934009MaRDI QIDQ2670463

Matthias Brugger, Andreas S. Schulz

Publication date: 11 March 2022

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

Full work available at URL: https://arxiv.org/abs/2104.14486

zbMATH Keywords

computational complexitytotal dual integralityintegralityGomory-chvátal cuts\(\{0, 1 / 2 \}\)-cuts

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the membership problem for the \({0, 1/2}\)-closure
• Matrices with the Edmonds-Johnson property
• On the membership problem for the elementary closure of a polyhedron
• Geometric algorithms and combinatorial optimization
• On certain polytopes associated with graphs
• \(\{ 0,\frac12\}\)-Chvátal-Gomory cuts
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• On the rational polytopes with Chvátal rank 1
• When the Gomory-chvátal closure coincides with the integer hull
• Edmonds polytopes and a hierarchy of combinatorial problems
• Claw-Free $t$-Perfect Graphs Can Be Recognized in Polynomial Time
• Facet Generating Techniques
• t-Perfection Is Always Strong for Claw-Free Graphs
• Integer Programming
• Odd Minimum Cut-Sets and b-Matchings
• The Graphs with All Subgraphs T-Perfect
• Strong T-Perfection of Bad-K₄ -Free Graphs
• Reducibility among Combinatorial Problems
• Maximum matching and a polyhedron with 0,1-vertices