The main subject of this thesis is the development of new geometric tools and techniques for solving classic problems within the geometry of
numbers and convex geometry. At a high level, the problems considered in this thesis concern the varied interplay between the continuous and
the discrete, an important theme within computer science and operations research. The first subject we consider is the study of cutting planes for non-linear integer programs. Cutting planes have been implemented to great
effect for linear integer programs, and so understanding their properties in more general settings is an important subject of study. As our contribution to this area, we show that Chvatal-Gomory closure of any compact convex set is a rational polytope. As a consequence, we
resolve an open problem of Schrijver (Ann. Disc. Math. `80) regarding the same question for irrational polytopes. The second subject of study is that of ellipsoidal approximation of convex bodies. Different such notions have been important to the
development of fundamental geometric algorithms: e.g. the ellipsoid method for convex optimization (enclosing ellipsoids), or random walk
methods for volume estimation (inertial ellipsoids). Here we consider the construction of an ellipsoid with good "covering" properties with respect to a convex body, known in convex geometry as the M-ellipsoid. As our contribution, we give two algorithms for constructing
M-ellipsoids, and provide an application to near-optimal deterministic volume estimation in the oracle model. Equipped with this new geometric tool, we move to the study of classic lattice problems in the geometry of numbers, namely the Shortest
(SVP) and Closest Vector Problems (CVP). Here we use M-ellipsoid coverings, combined with an algorithm of Micciancio and Voulgaris for CVP in the ℓ₂ norm (STOC `10), to obtain the first deterministic 2^O(ⁿ) time algorithm for the SVP in general norms. Combining this
algorithm with a novel lattice sparsification technique, we derive the first deterministic 2^O(ⁿ)(1+1/ϵ)ⁿ time algorithm for
(1+ϵ)-approximate CVP in general norms. For the next subject of study, we analyze the geometry of general integer programs. A central structural result in this area is Kinchine's flatness theorem, which states that every lattice free convex body has integer width bounded by a function of dimension. As our contribution, we build on the work Banaszczyk, using tools from lattice based cryptography, to give a new and tighter proof of the flatness theorem. Lastly, combining all the above techniques, we consider the study of algorithms for the Integer Programming Problem (IP). As our main
contribution, we give a new 2^O(ⁿ)nⁿ time algorithm for IP, which yields the fastest currently known algorithm for IP and improves on the classic works of Lenstra (MOR `83) and Kannan (MOR `87).
| Identifer | oai:union.ndltd.org:GATECH/oai:smartech.gatech.edu:1853/44807 |
| Date | 20 June 2012 |
| Creators | Dadush, Daniel Nicolas |
| Publisher | Georgia Institute of Technology |
| Source Sets | Georgia Tech Electronic Thesis and Dissertation Archive |
| Detected Language | English |
| Type | Dissertation |
Page generated in 0.0026 seconds