Binary cyclic transversal polytopes

DOI10.1137/24M1652027MaRDI QIDQ6932388zbMATH OpenFDO

Authors Jonas Frede, Volker Kaibel, Maximilian Merkert

Publication date 9 September 2025

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/24M1652027

zbMATH Keywords

combinatorial optimizationcyclic transversal polytopeextended formulationinteger programminglifted odd-set inequalitiesrelaxation hierarchy

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Combinatorial optimization (90C27) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Cites work

• A generalization of extension complexity that captures P
• Computational Complexity
• Exponential lower bounds for polytopes in combinatorial optimization
• Maximum matching and a polyhedron with 0,1-vertices
• On defining sets of vertices of the hypercube by linear inequalities
• On the cycle polytope of a binary matroid
• On the symmetric travelling salesman problem I: Inequalities
• The matching polytope has exponential extension complexity

This page was built for publication: Binary cyclic transversal polytopes

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