Cutting planes cannot approximate some integer programs

DOI10.1016/J.ORL.2012.03.008MaRDI QIDQ453048zbMATH OpenOpenAlexFDO

Authors Georg Schnitger, Stasys 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

interpolationcutting planesmonotone circuitsclique problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10)

Recommendations

• On cutting-plane proofs in combinatorial optimization
• On the rank of cutting-plane proof systems
• scientific article; zbMATH DE number 2086919
• Cutting-plane proofs in polynomial space
• On the complexity of cutting-plane proofs

Cites work

• scientific article; zbMATH DE number 4008289 (Why is no real title available?)
• Approximating maximum independent sets by excluding subgraphs
• Boolean function complexity. Advances and frontiers.
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Combinatorics of monotone computations
• Exponential Lower Bounds on the Lengths of Some Classes of Branch-and-Cut Proofs
• 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
• On cutting-plane proofs in combinatorial optimization
• On the complexity of cutting-plane proofs
• On the complexity of cutting-plane proofs using split cuts
• The monotone circuit complexity of Boolean functions
• The resolution complexity of independent sets and vertex covers in random graphs

Cited in

(4)

• On the redundancy of cutting planes for linear complementarity problems
• Computational Integer Programming and Cutting Planes
• Fenchel Cutting Planes for Integer Programs
• scientific article; zbMATH DE number 2086919 (Why is no real title available?)

This page was built for publication: Cutting planes cannot approximate some integer programs

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