Near-Optimal Deterministic Algorithms for Volume Computation and Lattice Problems via M-Ellipsoids
classification
💻 cs.CC
cs.DSmath.FA
keywords
deterministicalgorithmsconvexlatticeproblemsvolumealgorithmbodies
read the original abstract
We give a deterministic 2^{O(n)} algorithm for computing an M-ellipsoid of a convex body, matching a known lower bound. This has several interesting consequences including improved deterministic algorithms for volume estimation of convex bodies and the shortest and closest lattice vector problems under general norms.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.