Affordable Access

Cutting planes and the parameter cutwidth.

Publication Date
  • Mathematics


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.

There are no comments yet on this publication. Be the first to share your thoughts.


Seen <100 times

More articles like this

On cutting planes

Jan 01, 1980

Cutting planes and beyond

on Computers & Graphics Jan 01, 1997

Cutwidth I: A linear time fixed parameter algorith...

on Journal of Algorithms Jan 01, 2005
More articles like this..