Affordable Access

Cutting planes and the parameter cutwidth.

Authors
Publisher
Springer
Publication Date
Disciplines
  • Mathematics

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.

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

Statistics

Seen <100 times
0 Comments

More articles like this

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

Cutting Planes in Combinatorics

on European Journal of Combinator...
More articles like this..