Cutting Planes and the Parameter Cutwidth |
| |
Authors: | Stefan Dantchev Barnaby Martin |
| |
Affiliation: | 1. Department of Computer Science, University of Durham, Durham, UK 2. ??quipe de Logique Math??matique, CNRS UMR 7056, Universit?? Denis Diderot, Paris 7, France
|
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|