Cutting planes cannot approximate some integer programs

DOI10.1016/J.ORL.2012.03.008zbMATH Open1247.90197OpenAlexW2099116869MaRDI QIDQ453048FDOQ453048

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

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

zbMATH Keywords

interpolationcutting planesmonotone circuitsclique problem

Mathematics Subject Classification ID

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

Cites Work

• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Boolean function complexity. Advances and frontiers.
• Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
• Lower bounds for resolution and cutting plane proofs and monotone computations
• The monotone circuit complexity of Boolean functions
• Title not available (Why is that?)
• Lower bounds for cutting planes proofs with small coefficients
• On the complexity of cutting-plane proofs
• Approximating maximum independent sets by excluding subgraphs
• On cutting-plane proofs in combinatorial optimization
• Exponential Lower Bounds on the Lengths of Some Classes of Branch-and-Cut Proofs
• The resolution complexity of independent sets and vertex covers in random graphs
• Combinatorics of monotone computations
• On the complexity of cutting-plane proofs using split cuts

Cited In (4)

• Fenchel Cutting Planes for Integer Programs
• Title not available (Why is that?)
• On the redundancy of cutting planes for linear complementarity problems
• Computational Integer Programming and Cutting Planes

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)