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

DOI10.1016/J.ORL.2021.11.009MaRDI QIDQ2670463zbMATH OpenOpenAlexFDO

Authors 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

\(\{0, 1 / 2 \}\)-cutscomputational complexityGomory-chvátal cutsintegralitytotal dual integrality

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Recommendations

• On the membership problem for the \({0, 1/2}\)-closure
• When the Gomory-chvátal closure coincides with the integer hull
• The complexity of recognizing linear systems with certain integrality properties
• Deciding emptiness of the Gomory-Chvátal closure is NP-complete, even for a rational polyhedron containing no integer point
• On the NP-hardness of deciding emptiness of the split closure of a rational polytope in the 0,1 hypercube

Cites work

• \(\{ 0,\frac12\}\)-Chvátal-Gomory cuts
• \(t\)-perfection is always strong for claw-free graphs
• Claw-free t-perfect graphs can be recognized in polynomial time
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Edmonds polytopes and a hierarchy of combinatorial problems
• Facet generating techniques
• Geometric algorithms and combinatorial optimization
• scientific article; zbMATH DE number 3580570 (Why is no real title available?)
• scientific article; zbMATH DE number 3637616 (Why is no real title available?)
• scientific article; zbMATH DE number 3373541 (Why is no real title available?)
• Integer Programming
• Matrices with the Edmonds-Johnson property
• Maximum matching and a polyhedron with 0,1-vertices
• Odd Minimum Cut-Sets and b-Matchings
• On certain polytopes associated with graphs
• On the membership problem for the \({0, 1/2}\)-closure
• On the membership problem for the elementary closure of a polyhedron
• On the rational polytopes with Chvátal rank 1
• Reducibility among combinatorial problems
• Strong T-Perfection of Bad-K₄ -Free Graphs
• The Graphs with All Subgraphs T-Perfect
• When the Gomory-chvátal closure coincides with the integer hull

Cited in

(4)

• On the membership problem for the \({0, 1/2}\)-closure
• On the complexity of the integral closure
• On the Complexity of Recognizing Integrality and Total Dual Integrality of the $\{0,1/2\}$-Closure
• Primal separation and approximation for the \(\{0,1/2\}\)-closure

This page was built for publication: On the complexity of recognizing integrality and total dual integrality of the \(\{0,1/2\}\)-closure

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