A Connection Between Cutting Plane Theory and the Geometry of Numbers
Journal Article - Open Access
Carnegie Mellon University Pittsburgh United States
Pagination or Media Count:
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.
- Numerical Mathematics