Pitch, extension complexity, and covering problems

DOI10.1016/j.orl.2021.03.006OpenAlexW3152027881MaRDI QIDQ2060545

Xuan Zhang, Yuri Faenza, Bienstock, Daniel

Publication date: 13 December 2021

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

Full work available at URL: https://doi.org/10.1016/j.orl.2021.03.006

zbMATH Keywords

extension complexityseparation algorithmcovering problembounded pitchminimum knapsack

Mathematics Subject Classification ID

Numerical analysis (65-XX) Operations research, mathematical programming (90-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• On the extension complexity of combinatorial polytopes
• Expressing combinatorial optimization problems by linear programs
• The complexity of cover inequality separation
• The cut polytope and the Boolean quadric polytope
• Strengthening convex relaxations of 0/1-sets using Boolean formulas
• High degree sum of squares proofs, Bienstock-Zuckerberg hierarchy and CG cuts
• Approximate fixed-rank closures of covering problems
• Combinatorial Optimization
• Exponential Lower Bounds for Polytopes in Combinatorial Optimization
• Integer Programming
• Subset Algebra Lift Operators for 0-1 Integer Programming
• Nondeterministic Quantum Query and Communication Complexities
• Symmetry Matters for Sizes of Extended Formulations

This page was built for publication: Pitch, extension complexity, and covering problems