Accession Number:

AD1021089

Title:

A Connection Between Cutting Plane Theory and the Geometry of Numbers

Descriptive Note:

Journal Article - Open Access

Corporate Author:

Carnegie Mellon University Pittsburgh United States

Personal Author(s):

Report Date:

2002-06-01

Pagination or Media Count:

6.0

Abstract:

In 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 Chvatal and split cuts.

Descriptors:

Subject Categories:

  • Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE