Dantchev, Stefan and Martin, Barnaby (2012) 'Cutting planes and the parameter cutwidth.', Theory of computing systems., 51 (1). pp. 50-64.
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.
|Full text:||Full text not available from this repository.|
|Publisher Web site:||http://dx.doi.org/10.1007/s00224-011-9373-0|
|Record Created:||15 Dec 2009 10:35|
|Last Modified:||30 Nov 2012 13:14|
|Social bookmarking:||Export: EndNote, Zotero | BibTex|
|Usage statistics||Look up in GoogleScholar | Find in a UK Library|