Cutting planes cannot approximate some integer programs
From MaRDI portal
Publication:453048
DOI10.1016/j.orl.2012.03.008zbMath1247.90197OpenAlexW2099116869MaRDI QIDQ453048
Georg Schnitger, Stasys P. Jukna
Publication date: 18 September 2012
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.orl.2012.03.008
Cites Work
- Unnamed Item
- On the complexity of cutting-plane proofs
- Boolean function complexity. Advances and frontiers.
- On the complexity of cutting-plane proofs using split cuts
- The monotone circuit complexity of Boolean functions
- On cutting-plane proofs in combinatorial optimization
- Approximating maximum independent sets by excluding subgraphs
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- The resolution complexity of independent sets and vertex covers in random graphs
- Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
- Lower bounds for cutting planes proofs with small coefficients
- Lower bounds for resolution and cutting plane proofs and monotone computations
- Exponential Lower Bounds on the Lengths of Some Classes of Branch-and-Cut Proofs
- Combinatorics of monotone computations
This page was built for publication: Cutting planes cannot approximate some integer programs