From approximate to exact integer programming

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

Friedrich Eisenbrand, Thomas Rothvoß, Daniel Dadush

Publication date: 9 November 2023

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

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

Mathematics Subject Classification ID

Integer programming (90C10)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A randomized sieving algorithm for approximate integer programming
• Sampling methods for shortest vectors, closest vectors and successive minima
• An application of simultaneous diophantine approximation in combinatorial optimization
• Factoring polynomials with rational coefficients
• On integer points in polyhedra
• Geometric algorithms and combinatorial optimization
• Anti-Hadamard matrices, coin weighing, threshold gates, and indecomposable hypergraphs
• A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations
• Approximating Nash Equilibria and Dense Bipartite Subgraphs via an Approximate Version of Caratheodory's Theorem
• Integer Programming with a Fixed Number of Variables
• DYNAMIC PROGRAMMING AND A NEW FORMALISM IN THE THEORY OF INTEGRAL EQUATIONS
• Solving low-density subset sum problems
• Minkowski's Convex Body Theorem and Integer Programming
• A random polynomial-time algorithm for approximating the volume of convex bodies
• A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum
• Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints
• On Integer Programming and Convolution.
• A sieve algorithm for the shortest lattice vector problem
• Asymptotic Geometric Analysis, Part I
• Covering cubes and the closest vector problem
• Solving convex programs by random walks