2022/11/07 by Daniel Dadush, Dadush, Daniel, Friedrich Eisenbrand +3 · 1 citation
Computer Science · Engineering · #15A #52B #52C #68Q #68R #68W #90B #90C #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #G.1.6 #Optimization and Control (math.OC) #Optimization and Search Problems #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.2211.03859
openalex publication_date 2022/11/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Approximate integer programming is the following: For a convex body K ⊆ ℝn, either determine whether K ∩ ℤn is empty, or find an integer point in the convex body scaled by 2 from its center of gravity c. Approximate integer programming can be solved in time 2O(n) while the fastest known methods for exact integer programming run in time 2O(n) ⋅ nn. So far, there are no efficient methods for integer programming known that are based on approximate integer programming. Our main contribution are two such methods, each yielding novel complexity results. First, we show that an integer point x^* ∈ (K ∩ ℤn) can be found in time 2O(n), provided that the remainders of each component xi^* \modℓ for some arbitrarily fixed ℓ ≥ 5(n+1) of x^* are given. The algorithm is based on a cutting-plane technique, iteratively halving the volume of the feasible set. The cutting planes are determined via approximate integer programming. Enumeration of the possible remainders gives a 2O(n)nn algorithm for general integer programming. This matches the current best bound of an algorithm by Dadush (2012) that is considerably more involved. Our algorithm also relies on a new asymmetric approximate Carathéodory theorem that might be of interest on its own. Our second method concerns integer programming problems in equation-standard form Ax = b, 0 ≤ x ≤ u, x ∈ ℤn . Such a problem can be reduced to the solution of ∏i O(log ui +1) approximate integer programming problems. This implies, for example that knapsack or subset-sum problems with polynomial variable range 0 ≤ xi ≤ p(n) can be solved in time (log n)O(n). For these problems, the best running time so far was nn ⋅ 2O(n).