A Connection between Cutting Plane Theory and the Geometry of Num.pdf.pdf' (1.96 MB)
A Connection between Cutting Plane Theory and the Geometry of Numbers
journal contribution
posted on 2008-06-01, 00:00 authored by Gerard CornuejolsGerard Cornuejols, Yanjun LiIn this paper, we relate several questions about cutting planes to a fundamental problem in the
geometry of numbers, namely, the closest vector problem. Using this connection we show that the dominance,
membership and validity problems are NP-complete for Chvátal and split cuts.