Cutting-plane proofs in polynomial space

DOI10.1007/BF01580849MaRDI QIDQ1813835zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

system of linear inequalitiescutting plane proofrational coefficientsnon-existence of integral solutions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• On the complexity of cutting-plane proofs
• scientific article; zbMATH DE number 6829289
• On the rank of cutting-plane proof systems
• On cutting-plane proofs in combinatorial optimization
• scientific article; zbMATH DE number 512977

Cites work

• scientific article; zbMATH DE number 4006346 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3373541 (Why is no real title available?)
• A Cutting Plane Algorithm for the Linear Ordering Problem
• Cutting planes in combinatorics
• Edmonds polytopes and a hierarchy of combinatorial problems
• Edmonds polytopes and weakly hamiltonian graphs
• Facet generating techniques
• Geometric algorithms and combinatorial optimization.
• Integer Programming with a Fixed Number of Variables
• Minkowski's Convex Body Theorem and Integer Programming
• On Cutting Planes
• On Lovász' lattice reduction and the nearest lattice point problem
• On the complexity of cutting-plane proofs
• Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality
• Solving Large-Scale Zero-One Linear Programming Problems
• The intractability of resolution
• Valid Linear Inequalities for Fixed Charge Problems

Cited in

(22)

• scientific article; zbMATH DE number 6829289 (Why is no real title available?)
• scientific article; zbMATH DE number 1263234 (Why is no real title available?)
• On the rank of cutting-plane proof systems
• On cutting-plane proofs in combinatorial optimization
• scientific article; zbMATH DE number 6387509 (Why is no real title available?)
• Input Proofs and Rank One Cutting Planes
• Design and verify: a new scheme for generating cutting-planes
• On hardly linearly provable systems
• scientific article; zbMATH DE number 4024785 (Why is no real title available?)
• On the complexity of cutting-plane proofs using split cuts
• Design and verify: A new scheme for generating cutting-planes
• Lower bounds for cutting planes proofs with small coefficients
• Several notes on the power of Gomory-Chvátal cuts
• Stabbing planes
• Theoretical challenges towards cutting-plane selection
• Cutting planes cannot approximate some integer programs
• On semantic cutting planes with very small coefficients
• scientific article; zbMATH DE number 515726 (Why is no real title available?)
• Optimal length cutting plane refutations of integer programs
• Polynomially and superexponentially shorter proofs in fragments of arithmetic
• On the complexity of cutting-plane proofs
• Completeness of cutting planes revisited

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)