Strengthening convex relaxations of 0/1-sets using Boolean formulas
From MaRDI portal
Publication:2235155
DOI10.1007/s10107-020-01542-wzbMath1478.90060arXiv1711.01358OpenAlexW3042828318MaRDI QIDQ2235155
Samuel Fiorini, Stefan Weltge, Tony Huynh
Publication date: 20 October 2021
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1711.01358
Convex programming (90C25) Integer programming (90C10) Networks and circuits as models of computation; circuit complexity (68Q06)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- On the nonnegative rank of distance matrices
- Monotone circuits for monotone weighted threshold functions
- On the membership problem for the elementary closure of a polyhedron
- The complexity of cover inequality separation
- Maximum semidefinite and linear extension complexity of families of polytopes
- Relating monotone formula size and monotone depth of Boolean functions
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- High degree sum of squares proofs, Bienstock-Zuckerberg hierarchy and CG cuts
- Some \(0/1\) polytopes need exponential size extended formulations
- Edmonds polytopes and a hierarchy of combinatorial problems
- Approximate fixed-rank closures of covering problems
- Exponential Lower Bounds for Polytopes in Combinatorial Optimization
- On Some Polytopes Contained in the 0,1 Hypercube that Have a Small Chvátal Rank
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Monotone Circuits for Connectivity Require Super-Logarithmic Depth
- Improving Integrality Gaps via Chvátal-Gomory Rounding
- Monotone Circuits for the Majority Function
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Disjunctive Programming
- Monotone circuits for matching require linear depth
- Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits
- Extension Complexity of Independent Set Polytopes
- The Matching Polytope has Exponential Extension Complexity
- Subset Algebra Lift Operators for 0-1 Integer Programming
- Characterizing Polytopes in the 0/1-Cube with Bounded Chvátal-Gomory Rank
- No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ
