Integer programming, lattice algorithms, and deterministic volume estimation

Integer programming;Lattice algorithms;Convex geometry;Volume estimation

Dadush, Daniel Nicolas ; Industrial and Systems Engineering

University:Georgia Institute of Technology

Department:Industrial and Systems Engineering

关键词: Integer programming;    Lattice algorithms;    Convex geometry;    Volume estimation;   

Others  :  https://smartech.gatech.edu/bitstream/1853/44807/1/dadush_daniel_n_201208_phd.pdf

美国|英语

来源: SMARTech Repository

【 摘 要 】

The main subject of this thesis is the development of new geometric tools and techniques for solving classic problems within the geometry ofnumbers and convex geometry. At a high level, the problems considered in this thesis concern the varied interplay between the continuous andthe 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 greateffect 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, weresolve 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 thedevelopment of fundamental geometric algorithms: e.g. the ellipsoid method for convex optimization (enclosing ellipsoids), or random walkmethods 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 constructingM-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 thisalgorithm 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 maincontribution, 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).