Abstract
Approximate integer programming is the following: For a given convex body \(K \subseteq \mathbb {R}^n\), either determine whether \(K \cap \mathbb {Z}^n\) is empty, or find an integer point in the convex body \(2\cdot (K - c) +c\) which is K, scaled by 2 from its center of gravity c. Approximate integer programming can be solved in time \(2^{O(n)}\) while the fastest known methods for exact integer programming run in time \(2^{O(n)} \cdot n^n\). 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^* \in (K \cap \mathbb {Z}^n)\) can be found in time \(2^{O(n)}\), provided that the remainders of each component \(x_i^* \mod \ell \) for some arbitrarily fixed \(\ell \ge 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 \(2^{O(n)}n^n\) 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 standard equation form \(Ax = b, 0 \le x \le u, \, x \in \mathbb {Z}^n\) . Such a problem can be reduced to the solution of \(\prod _i O(\log u_i +1)\) approximate integer programming problems. This implies, for example that knapsack or subset-sum problems with polynomial variable range \(0 \le x_i \le p(n)\) can be solved in time \((\log n)^{O(n)}\). For these problems, the best running time so far was \(n^n \cdot 2^{O(n)}\).
A full version of this paper can be found under https://arxiv.org/abs/2211.03859.
D. Dadush—Supported by ERC Starting Grant no. 805241-QIP.
F. Eisenbrand—Supported by the Swiss National Science Foundation (SNSF) grant 185030 and 207365.
T. Rothvoss—Supported by NSF CAREER grant 1651861 and a David & Lucile Packard Foundation Fellowship.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Miklós Ajtai, R.K., Sivakumar, D.: A sieve algorithm for the shortest lattice vector problem. In: Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, pp. 601–610 (2001)
Alon, N., Vũ, V.H.: Anti-hadamard matrices, coin weighing, threshold gates, and indecomposable hypergraphs. J. Comb. Theory Ser. A 79(1), 133–160 (1997)
Artstein-Avidan, S., Giannopoulos, A., Milman, V.D.: Asymptotic geometric analysis. Part I, Volume 202 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI (2015)
Barman, S.: Approximating nash equilibria and dense bipartite subgraphs via an approximate version of Caratheodory’s theorem. In: Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, pp. 361–369 (2015)
Bellman, R.: Dynamic programming. Science 153(3731), 34–37 (1966)
Bertsimas, D., Vempala, S.: Solving convex programs by random walks. J. ACM (JACM) 51(4), 540–556 (2004)
Blömer, J., Naewe, S.: Sampling methods for shortest vectors, closest vectors and successive minima. Theor. Comput. Sci. 410(18), 1648–1665 (2009)
Bringmann, K.: A near-linear pseudopolynomial time algorithm for subset sum. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1073–1084. SIAM (2017)
Cook, W., Hartmann, M., Kannan, R., McDiarmid, C.: On integer points in polyhedra. Combinatorica 12(1), 27–37 (1992)
Dadush, D.: Integer Programming, Lattice Algorithms, and Deterministic Volume Estimation. Georgia Institute of Technology (2012)
Dadush, D.: A randomized sieving algorithm for approximate integer programming. Algorithmica 70(2), 208–244 (2014)
Dyer, M., Frieze, A., Kannan, R.: A random polynomial-time algorithm for approximating the volume of convex bodies. J. ACM 38(1), 1–17 (1991)
Eisenbrand, F., Hähnle, N., Niemeier, M.: Covering cubes and the closest vector problem. In: Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry, pp. 417–423 (2011)
Eisenbrand, F., Weismantel, R.: Proximity results and faster algorithms for integer programming using the Steinitz lemma. ACM Trans. Algorithms (TALG) 16(1), 1–14 (2019)
Frank, A., Tardos, É.: An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica 7(1), 49–65 (1987)
Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Algorithms and Combinatorics, vol. 2. Springer, Heidelberg (1988). https://doi.org/10.1007/978-3-642-78240-4
Jansen, K., Rohwedder, L.: On integer programming and convolution. In: 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2018)
Jiang, H.: Minimizing convex functions with integral minimizers. In: SODA, pp. 976–985. SIAM (2021)
Kannan, R.: Minkowski’s convex body theorem and integer programming. Math. Oper. Res. 12(3), 415–440 (1987)
Knop, D., Pilipczuk, M., Wrochna, M.: Tight complexity lower bounds for integer linear programming with few constraints. ACM Trans. Comput. Theory (TOCT) 12(3), 1–19 (2020)
Lagarias, J.C., Odlyzko, A.M.: Solving low-density subset sum problems. J. ACM (JACM) 32(1):229–246 (1985)
Lenstra, A.K., Lenstra, H.W., Lovász, L.: Factoring polynomials with rational coefficients. Mathematische annalen 261(ARTICLE), 515–534 (1982)
Lenstra Jr., H.W.: Integer programming with a fixed number of variables. Math. Oper. Res. 8(4), 538–548 (1983)
Micciancio, D., Goldwasser, S.: Complexity of lattice problems - a cryptograhic perspective. The Kluwer International Series in Engineering and Computer Science, vol. 671. Springer, New York (2002). https://doi.org/10.1007/978-1-4615-0897-7
Micciancio, D., Voulgaris, P.: A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations. In: Proceedings of the Forty-Second ACM Symposium on Theory of Computing, pp. 351–358 (2010)
Mirrokni, V., Leme, R.P., Vladu, A., Wong, S.C.: Tight bounds for approximate Carathéodory and beyond. In: International Conference on Machine Learning, pp. 2440–2448. PMLR (2017)
Nemhauser, G.L., Wolsey, L.A.: Integer programming. In: Nemhauser, G.L., et al. (eds.) Optimization. Handbooks in Operations Research and Management Science, chapter VI, vol. 1, pp. 447–527. Elsevier (1989)
Novikoff, A.B.: On convergence proofs for perceptrons. Technical report, Office of Naval Research, Washington, D.C. (1963)
Polak, A., Rohwedder, L., Węgrzycki, K.: Knapsack and subset sum with small items. In: 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), number CONF, pp. 106–1. Schloss Dagstuhl-Leibniz-Zentrum für Informatik (2021)
Schrijver, A.: Polyhedral combinatorics. In: Graham, R., Grötschel, M., Lovász, L. (eds.) Handbook of Combinatorics, chapter 30, vol. 2, pp. 1649–1704. Elsevier (1995)
Schrijver, A.: Theory of Linear and Integer Programming. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, Hoboken (1999)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Dadush, D., Eisenbrand, F., Rothvoss, T. (2023). From Approximate to Exact Integer Programming. In: Del Pia, A., Kaibel, V. (eds) Integer Programming and Combinatorial Optimization. IPCO 2023. Lecture Notes in Computer Science, vol 13904. Springer, Cham. https://doi.org/10.1007/978-3-031-32726-1_8
Download citation
DOI: https://doi.org/10.1007/978-3-031-32726-1_8
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-32725-4
Online ISBN: 978-3-031-32726-1
eBook Packages: Computer ScienceComputer Science (R0)