Cutting-plane proofs in polynomial space
DOI10.1007/BF01580849zbMATH Open0735.90048OpenAlexW1990237439MaRDI QIDQ1813835FDOQ1813835
Authors: William Cook 
Publication date: 25 June 1992
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01580849
Recommendations
system of linear inequalitiescutting plane proofrational coefficientsnon-existence of integral solutions
Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60)
Cites Work
- Title not available (Why is that?)
- Geometric algorithms and combinatorial optimization.
- Integer Programming with a Fixed Number of Variables
- Solving Large-Scale Zero-One Linear Programming Problems
- Minkowski's Convex Body Theorem and Integer Programming
- Title not available (Why is that?)
- On the complexity of cutting-plane proofs
- On Lovász' lattice reduction and the nearest lattice point problem
- Edmonds polytopes and a hierarchy of combinatorial problems
- Valid Linear Inequalities for Fixed Charge Problems
- On Cutting Planes
- The intractability of resolution
- A Cutting Plane Algorithm for the Linear Ordering Problem
- Edmonds polytopes and weakly hamiltonian graphs
- Title not available (Why is that?)
- Cutting planes in combinatorics
- Facet generating techniques
- Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality
Cited In (22)
- Title not available (Why is that?)
- Lower bounds for cutting planes proofs with small coefficients
- Title not available (Why is that?)
- On cutting-plane proofs in combinatorial optimization
- On semantic cutting planes with very small coefficients
- Theoretical challenges towards cutting-plane selection
- Optimal length cutting plane refutations of integer programs
- Stabbing planes
- On the complexity of cutting-plane proofs
- On the rank of cutting-plane proof systems
- Design and verify: A new scheme for generating cutting-planes
- Cutting planes cannot approximate some integer programs
- On hardly linearly provable systems
- Several notes on the power of Gomory-Chvátal cuts
- Design and verify: a new scheme for generating cutting-planes
- On the complexity of cutting-plane proofs using split cuts
- Completeness of cutting planes revisited
- Polynomially and superexponentially shorter proofs in fragments of arithmetic
- Title not available (Why is that?)
- Title not available (Why is that?)
- Input Proofs and Rank One Cutting Planes
- Title not available (Why is that?)
This page was built for publication: Cutting-plane proofs in polynomial space
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1813835)
