On the complexity of cutting-plane proofs
From MaRDI portal
Publication:580175
DOI10.1016/0166-218X(87)90039-4zbMath0625.90056MaRDI QIDQ580175
György Turán, William Cook, Collette R. Coullard
Publication date: 1987
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
68Q25: Analysis of algorithms and problem complexity
90C10: Integer programming
90C05: Linear programming
Related Items
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, Polyhedral techniques in combinatorial optimization I: Theory, Resolution proofs of generalized pigeonhole principles, On meta complexity of propositional formulas and propositional proofs, On the Chvátal rank of the pigeonhole principle, \texttt{SymChaff}: Exploiting symmetry in a structure-aware satisfiability solver, On cutting-plane proofs in combinatorial optimization, An exponential lower bound for the size of monotone real circuits, Testing satisfiability of CNF formulas by computing a stable set of points, Cutting-plane proofs in polynomial space, Cutting planes, connectivity, and threshold logic, Upper bounds on complexity of Frege proofs with limited use of certain schemata, Several notes on the power of Gomory-Chvátal cuts, Resolution Width and Cutting Plane Rank Are Incomparable, Sensitivity theorems in integer linear programming, Discretely ordered modules as a first-order extension of the cutting planes proof system
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Recursive number theory. A development of recursive arithmetic in a logic-free equation calculus
- Cutting planes in combinatorics
- The intractability of resolution
- On Lovász' lattice reduction and the nearest lattice point problem
- Edmonds polytopes and a hierarchy of combinatorial problems
- Facet Generating Techniques
- Integer Programming with a Fixed Number of Variables
- Sensitivity theorems in integer linear programming
- On Cutting Planes
- An observation on the structure of production sets with indivisibilities
- A Theorem Concerning the Integer Lattice
- Determining the Stability Number of a Graph
- The relative efficiency of propositional proof systems
- Propositional representation of arithmetic proofs (Preliminary Version)
- A Machine-Oriented Logic Based on the Resolution Principle
- The Specialization of Programs by Theorem Proving
- Edmonds polytopes and weakly hamiltonian graphs
