From approximate to exact integer programming

DOI10.1007/S10107-024-02084-1MaRDI QIDQ7019071zbMATH OpenFDO

Authors Daniel Dadush, Friedrich Eisenbrand, Thomas Rothvoß

Publication date 5 March 2025

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S10107-024-02084-1

zbMATH Keywords

latticesinteger programmingconvex geometry

Mathematics Subject Classification ID

Integer programming (90C10)

Cites work

• scientific article; zbMATH DE number 2120513 (Why is no real title available?)
• scientific article; zbMATH DE number 863499 (Why is no real title available?)
• scientific article; zbMATH DE number 3225500 (Why is no real title available?)
• scientific article; zbMATH DE number 7788399 (Why is no real title available?)
• A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations
• A near-linear pseudopolynomial time algorithm for subset sum
• A random polynomial-time algorithm for approximating the volume of convex bodies
• A randomized sieving algorithm for approximate integer programming
• A sieve algorithm for the shortest lattice vector problem
• An application of simultaneous diophantine approximation in combinatorial optimization
• Anti-Hadamard matrices, coin weighing, threshold gates, and indecomposable hypergraphs
• Approximating Nash equilibria and dense bipartite subgraphs via an approximate version of Carathéodory's theorem
• Asymptotic geometric analysis. I
• Covering cubes and the closest vector problem
• Factoring polynomials with rational coefficients
• Geometric algorithms and combinatorial optimization
• Integer Programming with a Fixed Number of Variables
• Minkowski's Convex Body Theorem and Integer Programming
• On integer points in polyhedra
• On integer programming and convolution
• Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma
• Quantitative estimates of the convergence of the empirical covariance matrix in log-concave ensembles
• Random walks and anO*(n5) volume algorithm for convex bodies
• Sampling methods for shortest vectors, closest vectors and successive minima
• Solving convex programs by random walks
• Solving low-density subset sum problems
• The subspace flatness conjecture and faster integer programming
• Tight complexity lower bounds for integer linear programming with few constraints

Cited in

(1)

• Parameterized algorithms for block-structured integer programs with large entries

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 Q7019071)