A randomized sieving algorithm for approximate integer programming
From MaRDI portal
Publication:486990
DOI10.1007/S00453-013-9834-8zbMATH Open1311.90076OpenAlexW2093079548MaRDI QIDQ486990FDOQ486990
Publication date: 19 January 2015
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-013-9834-8
Recommendations
- A \(O(1/\epsilon ^{2})^{n }\)-time sieving algorithm for approximate integer programming
- Fast integer programming in fixed dimension
- Minkowski's Convex Body Theorem and Integer Programming
- Las Vegas algorithms for linear and integer programming when the dimension is small
- Some sieving algorithms for lattice problems
Cites Work
- A sieve algorithm for the shortest lattice vector problem
- Geometric algorithms and combinatorial optimization
- Entropy and asymptotic geometry of non-symmetric convex bodies
- Isoperimetric problems for convex bodies and a localization lemma
- Integer Programming with a Fixed Number of Variables
- Outline of an algorithm for integer solutions to linear programs
- Minkowski's Convex Body Theorem and Integer Programming
- Title not available (Why is that?)
- Parametric Integer Programming in Fixed Dimension
- New bounds in some transference theorems in the geometry of numbers
- A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed
- Covering minima and lattice-point-free convex bodies
- A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations
- The Flatness Theorem for Nonsymmetric Convex Bodies via the Local Theory of Banach Spaces
- On Lovász' lattice reduction and the nearest lattice point problem
- Inequalities for convex bodies and polar reciprocal lattices in \(\mathbb{R}^ n\). II: Application of \(K\)-convexity
- Distances between non-symmetric convex bodies and the \(MM^*\)-estimate
- Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings
- Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice
- Concentration of mass on isotropic convex bodies
- Sampling methods for shortest vectors, closest vectors and successive minima
- Approximating shortest lattice vectors is not harder than approximating closest lattice vectors
- A new Lenstra-type algorithm for quasiconvex polynomial integer minimization with complexity \(2^{O(n\log n)}\)
- Complexity of integer quasiconvex polynomial optimization
- Some Sieving Algorithms for Lattice Problems
- Title not available (Why is that?)
- Covering cubes and the closest vector problem
Cited In (3)
This page was built for publication: A randomized sieving algorithm for approximate integer programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q486990)
