Standard

Several notes on the power of Gomory-Chvátal cuts. / Hirsch, Edward A.; Kojevnikov, Arist.

в: Annals of Pure and Applied Logic, Том 141, № 3, 01.09.2006, стр. 429-436.

Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование

Harvard

Hirsch, EA & Kojevnikov, A 2006, 'Several notes on the power of Gomory-Chvátal cuts', Annals of Pure and Applied Logic, Том. 141, № 3, стр. 429-436. https://doi.org/10.1016/j.apal.2005.12.006

APA

Hirsch, E. A., & Kojevnikov, A. (2006). Several notes on the power of Gomory-Chvátal cuts. Annals of Pure and Applied Logic, 141(3), 429-436. https://doi.org/10.1016/j.apal.2005.12.006

Vancouver

Hirsch EA, Kojevnikov A. Several notes on the power of Gomory-Chvátal cuts. Annals of Pure and Applied Logic. 2006 Сент. 1;141(3):429-436. https://doi.org/10.1016/j.apal.2005.12.006

Author

Hirsch, Edward A. ; Kojevnikov, Arist. / Several notes on the power of Gomory-Chvátal cuts. в: Annals of Pure and Applied Logic. 2006 ; Том 141, № 3. стр. 429-436.

BibTeX

@article{c2a872396a754172b26c5d947e181a37,
title = "Several notes on the power of Gomory-Chv{\'a}tal cuts",
abstract = "We prove that the Cutting Plane proof system based on Gomory-Chv{\'a}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{\'i}{\v c}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).",
keywords = "Integer programming, Propositional proof complexity",
author = "Hirsch, {Edward A.} and Arist Kojevnikov",
year = "2006",
month = sep,
day = "1",
doi = "10.1016/j.apal.2005.12.006",
language = "English",
volume = "141",
pages = "429--436",
journal = "Annals of Pure and Applied Logic",
issn = "0168-0072",
publisher = "Elsevier",
number = "3",

}

RIS

TY - JOUR

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

AU - Hirsch, Edward A.

AU - Kojevnikov, Arist

PY - 2006/9/1

Y1 - 2006/9/1

N2 - 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).

AB - 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).

KW - Integer programming

KW - Propositional proof complexity

UR - http://www.scopus.com/inward/record.url?scp=33646872032&partnerID=8YFLogxK

U2 - 10.1016/j.apal.2005.12.006

DO - 10.1016/j.apal.2005.12.006

M3 - Article

AN - SCOPUS:33646872032

VL - 141

SP - 429

EP - 436

JO - Annals of Pure and Applied Logic

JF - Annals of Pure and Applied Logic

SN - 0168-0072

IS - 3

ER -

ID: 49828142