Skip to main content

Research Repository

Advanced Search

Cutting Planes and the Parameter Cutwidth

Dantchev, Stefan; Martin, Barnaby

Authors

Barnaby Martin



Contributors

K. Ambos-Spies
Editor

B. Löwe
Editor

W. Merkle
Editor

Abstract

We introduce the parameter cutwidth for the Cutting Planes (CP) system of Gomory and Chvátal. We provide linear lower bounds on cutwidth for two simple polytopes. Considering CP as a propositional refutation system, one can see that the cutwidth of a CNF contradiction F is always bound above by the Resolution width of F. We provide an example proving that the converse fails: there is an F which has constant cutwidth, but has Resolution width Ω(n). Following a standard method for converting an FO sentence ψ, without finite models, into a sequence of CNFs, F ψ,n , we provide a classification theorem for CP based on the sum cutwidth plus rank. Specifically, the cutwidth+rank of F ψ,n is bound by a constant c (depending on ψ only) iff ψ has no (infinite) models. This result may be seen as a relative of various gap theorems extant in the literature.

Citation

Dantchev, S., & Martin, B. (2012). Cutting Planes and the Parameter Cutwidth. Theory of Computing Systems, 51(1), 50-64. https://doi.org/10.1007/s00224-011-9373-0

Journal Article Type Article
Publication Date 2012-07
Deposit Date Dec 15, 2009
Journal Theory of Computing Systems
Print ISSN 1432-4350
Electronic ISSN 1433-0490
Publisher Springer
Peer Reviewed Peer Reviewed
Volume 51
Issue 1
Pages 50-64
DOI https://doi.org/10.1007/s00224-011-9373-0


You might also like



Downloadable Citations