A Sieving Algorithm for Approximate Integer Programming
Integer programming (IP) is a classic problem in discrete optimization with a worst-case complexity that is NP-Complete. Complexity and algorithms for IP involve solving in polynomial time with different techniques developed by researchers like Lenstra and Kannan. Feasibility of solutions in binary vs. general integers presents challenges and adaptations based on the problem's geometry.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
A Sieving Algorithm for Approximate Integer Programming Daniel Dadush, CWI
Integer Programming (IP) min??? s.t. ?? ? ? ? ? ? ? ? variables, ? constraints Classic Problem in Discrete Optimization: Danzig, Fulkerson, Johnson `54 Gomory `58, Lenstra `82, Kannan `87,
Complexity & Algorithms IP is NP-Complete (even with just binary variables). We do not expect polynomial time algorithms. Question: What is worst case complexity of IP?
Complexity & Algorithms min ?? ? s.t. ?? ?,? ? ? H. Lenstra `83: IP can be solved in time poly ? 2? ?3 using poly ? space, where ? is the input length. Kannan `87: Running time can be reduced to poly ? 2?(?)?2.5?. Current Fastest: 2?(?)?? time, 2?(?) space [D. `12].
Complexity & Algorithms min ?? ? s.t. ?? ?,? ? ? H. Lenstra `83: IP can be solved in time poly ? 2? ?3 using poly ? space, where ? is the input length. Kannan `87: Running time can be reduced to poly ? 2?(?)?2.5?. Developed tools for lattice problems which have found applications in Cryptanalysis, Cryptography, Coding Theory, Number Theory, .
Integer Programming Feasibility Find feasible solution to ?? ?,? ? ? or decide that no solution exists. ? = {? ? ?:?? ?} (continuous relaxation) ? ? 0 ?
Binary vs General Integer Find feasible solution to ?? ?,? ? 0,1? or decide that no solution exists. Total enumeration is easy (2? time). ? 0 ?
Binary vs General Integer Find feasible solution to ?? ?,? ? ? or decide that no solution exists. No easy analog of total enumeration. ? ? 0 ?
Binary vs General Integer Find feasible solution to ?? ?,? ? ? or decide that no solution exists. Need to adapt to the geometry of ?. ? ? 0 ?
Binary vs General Integer Find feasible solution to ?? ?,? ? ? or decide that no solution exists. Question: Is there a 2?(?) time algorithm for IP? ? ? 0 ?
Relaxing the Model Pick ? ? ?, ? > 0. Find solution to ?? ? + ?(? ??),? ? ? or decide system is infeasible for ? = 0. 1+? scaling of ? about ? ? ? ? 0 ?
Relaxing the Model Pick ? ? ?, ? > 0. Find solution to ?? ? + ?(? ??),? ? ? or decide system is infeasible for ? = 0. 1+? scaling of ? about ? ? ? ? 0 ?
Result: Approximate Feasibility 1 2, ? the center of mass of ?, Algorithm:0 < ? either (1) finds ? ? ?in (1+?) scaling of ? about c, or (2) decides that ? is integer free, ?(?) time, space and randomness. 1 ? using ? ? ?
Result: Approximate Optimization 1 2, ? < 0, objective ? ? ?, Algorithm:0 < ? either (1) decides that ? is integer free or (2) finds ? ? ?in ? + ?(? ?)( blowup of ?), ? ? ? ???? ??? ?, satisfying min ?(?)log1 1 ? using ? time, space, randomness. ? ? ?
Center of Mass Convex body ? ? ?? Center of Mass: c = ?? vol(?) ? 1 ? ?=1 Algorithm: c ?? ?? are iid uniform from ?[Dyer-Frieze-Kannan 89]. ?7 ?5 ?2 ? ?3 ?4 ? ?1 ?6
Center of Mass Convex body ? ? ?? Center of Mass: c = ?? vol(?) Crucial Property [Milman-Pajor `00]: vol ? 2?vol(? 2? ?)(near symmetry) ? ? 2? ?
Kinchines Flatness Theorem Algorithm: Given ? ?. Using 2?(?) time and space (1) either finds ? ? ? ?, or ? ?
Kinchines Flatness Theorem Algorithm: Given ? ?. Using 2?(?) time and space (1) either finds ? ? ? ?, or (2) find ? ? ? {0}satisfying width?? = max? ? ? ?,? min? ? ? ?,? (?4/3) [Kinchine 48, Babai 86, Lenstra-Lagarias-Schnorr 87, Hastad 88, Kannan-L0vasz 88, Banasczyk 96, Rudelson 00] ? ? ytx=1 ytx=2 ytx=0
Kinchines Flatness Theorem Best known bounds for Flatness Constants: 1. Ellipsoids: ?(?) = (?) 2. General Bodies: ? ? = ? 4 3 [Kinchine 48, Lenstra-Lagarias-Schnorr 87, Kannan-L0vasz 88, Banasczyk et al 99, Rudelson 00] ? ?
Norms and Convex Bodies Symmetric convex body ? ? (? = ?). ?-norm: ?? inf {? 0:? ? ??} ? ?? ? ? = {? ? ?: ? is unit ball of ? ?? 1} 0 -? 1. ? + ?? ??+ ?? (triangle inequality) 2. ???= ? ??,? 0 (homogeneity) 3. ??= ?? (symmetry)
Norms and Convex Bodies Convex body ? ? containing origin in its interior. ?-norm: ?? inf {? 0:? ? ??} ? ?? ? ? = {? ? ?: ? is unit ball of ? ?? 1} 0 1. ? + ?? ??+ ?? (triangle inequality) 2. ???= ? ??,? 0 (homogeneity) 3. ??= ?? (symmetry)
Norms and Convex Bodies Convex body ? ? containing origin in its interior. ?-norm: ?? inf {? 0:? ? ??} ? ?? ? ? = {? ? ?: ? is unit ball of ? ?? 1} 0 1. ? + ?? ??+ ?? (triangle inequality) 2. ???= ? ??,? 0 (homogeneity) 3. vol ? 2?(?)vol(? ?) (near-symmetry)
Shortest Vector Problem (SVP) Given: norm ? in ?. Goal: Find ? ? ? {0} minimizing ?K. ? ? 0 ? -?
Closest Vector Problem (CVP) Given: target ?, norm ? in ?. Goal: Find ? ? ? minimizing ? ??. ? ? ? ?
Main Tools Algorithms: Near symmetric norm ?. (1) Finds shortest non-zero integer vector under ? using 2?(?) time, space, and randomness. ? ? 0
Main Tools Algorithms: Near symmetric norm ?. (1) Finds shortest non-zero integer vector under ? using 2?(?) time, space, and randomness. (2) 0 < ? 1 2, ? ? ?. Finds 1+? -approximate closest integer vector to t under ? using 1/??(?) . ? ? ?
Approx. IP Approx. CVP Algorithm: 1. Estimate center of mass ? of ? (via uniform sampling). 2. Solve (1 + ?)-approximate Closest Vector Problem with target ? under ? ? (near symmetric). 3. If ? ?? ? 1 + ?, return y. Else, return ? ?= . ? ? ? ?
The Randomized Sieve General Idea: Sample exponentially many perturbed integer points, combine them to get closer & closer (shorter & shorter) integer vectors. Ajtai-Kumar-Sivakumar `0o+`01: Developed randomized sieving strategy for SVP and 1 + ? -CVP for the ?2 norm. Blomer-Naewe `07: Refined and extended AKS approach to get SVP and 1 + ? -CVP for ?? norms. Arvind-Joglekar `09: SVP for symmetric norms. This paper: SVP & 1 + ? -CVP for near symmetric norms.
Recent work ? time, 1 ? [D. Vempala `12, D. `12]: Deterministic 2?(?) space algorithm for (1+?) CVP. Conclusions 1. Presented approximate IP model and gave single exponential time algorithm to solve it. 2. Generalized the AKS randomized sieve to nearly all norms. Open Problems 1. Achieve same time complexity using poly(?) space? 2. 2?(?) time algorithm for IP?
