Cutting planes cannot approximate some integer programs

DOI10.1016/j.orl.2012.03.008zbMath1247.90197MaRDI 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

zbMATH Keywords

interpolation; monotone circuits; cutting planes; clique problem

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C10: Integer programming

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