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

Edward A. Hirsch, Arist Kojevnikov

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים

4 ציטוטים ‏(Scopus)

תקציר

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

שפה מקוריתאנגלית
עמודים (מ-עד)429-436
מספר עמודים8
כתב עתAnnals of Pure and Applied Logic
כרך141
מספר גיליון3
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - ספט׳ 2006
פורסם באופן חיצוניכן

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Several notes on the power of Gomory-Chvátal cuts'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי