From approximate to exact integer programming

DOI10.1007/978-3-031-32726-1_8arXiv2211.03859OpenAlexW4377200011MaRDI QIDQ6085992FDOQ6085992

Authors: Daniel Dadush, Friedrich Eisenbrand, Thomas Rothvoß 

Publication date: 9 November 2023

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Abstract: Approximate integer programming is the following: For a convex body $Ksubseteqmathbb{R}^n$, either determine whether $Kcapmathbb{Z}^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 $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^{\ast }in(Kcapmathbb{Z}^n)$ can be found in time $2^{O(n)}$, provided that the remainders of each component $x_i^{\ast }modell$ for some arbitrarily fixed $ellgeq5(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'eodory theorem that might be of interest on its own. Our second method concerns integer programming problems in equation-standard form $Ax=b,0leqxlequ,,xinmathbb{Z}^n$ . Such a problem can be reduced to the solution of $pro{d}_{i}O(log{u}_i+1)$ approximate integer programming problems. This implies, for example that knapsack or subset-sum problems with polynomial variable range $0leq{x}_{i}leqp(n)$ can be solved in time $(logn{)}^{O(n)}$. For these problems, the best running time so far was $n^{n}cdot{2}^{O(n)}$.

Full work available at URL: https://arxiv.org/abs/2211.03859

Recommendations

• scientific article; zbMATH DE number 549930
• scientific article; zbMATH DE number 3976781
• scientific article; zbMATH DE number 3972639
• An approximate algorithm for nonlinear integer programming
• An algorithm of internal feasible directions for linear integer programming

Mathematics Subject Classification ID

Integer programming (90C10)

Cites Work

• A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations
• A sieve algorithm for the shortest lattice vector problem
• Geometric algorithms and combinatorial optimization
• Asymptotic geometric analysis. I
• Factoring polynomials with rational coefficients
• Integer Programming with a Fixed Number of Variables
• Minkowski's Convex Body Theorem and Integer Programming
• A random polynomial-time algorithm for approximating the volume of convex bodies
• Solving convex programs by random walks
• Title not available (Why is that?)
• An application of simultaneous diophantine approximation in combinatorial optimization
• Approximating Nash equilibria and dense bipartite subgraphs via an approximate version of Carathéodory's theorem
• Solving low-density subset sum problems
• On integer points in polyhedra
• Anti-Hadamard matrices, coin weighing, threshold gates, and indecomposable hypergraphs
• Title not available (Why is that?)
• Sampling methods for shortest vectors, closest vectors and successive minima
• A randomized sieving algorithm for approximate integer programming
• Covering cubes and the closest vector problem
• DYNAMIC PROGRAMMING AND A NEW FORMALISM IN THE THEORY OF INTEGRAL EQUATIONS
• Tight complexity lower bounds for integer linear programming with few constraints
• Title not available (Why is that?)
• Title not available (Why is that?)
• A near-linear pseudopolynomial time algorithm for subset sum
• Title not available (Why is that?)
• On integer programming and convolution

Cited In (5)

• Compact representation of near-optimal integer programming solutions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma
• Title not available (Why is that?)

This page was built for publication: From approximate to exact integer programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6085992)