Several notes on the power of Gomory-Chvátal cuts

Edward A. Hirsch, Arist Kojevnikov

Research output

2 Citations (Scopus)

Abstract

We prove that the Cutting Plane proof system based on Gomory-Chvátal cuts polynomially simulates the lift-and-project system with integer coefficients written in unary. The restriction on the coefficients can be omitted when using Krajíček's cut-free Gentzen-style extension of both systems. We also prove that Tseitin tautologies have short proofs in this extension (of any of these systems and with any coefficients).

Original languageEnglish
Pages (from-to)429-436
Number of pages8
JournalAnnals of Pure and Applied Logic
Volume141
Issue number3
DOIs
Publication statusPublished - 1 Sep 2006

Scopus subject areas

  • Logic

Fingerprint Dive into the research topics of 'Several notes on the power of Gomory-Chvátal cuts'. Together they form a unique fingerprint.

  • Cite this