Near-optimal deterministic algorithms for volume computation via M-ellipsoids

DOI10.1073/pnas.1203863110zbMath1292.52018arXiv1201.5972OpenAlexW1777564763WikidataQ46087341 ScholiaQ46087341MaRDI QIDQ5170985

Daniel Dadush, Santosh Vempala

Publication date: 25 July 2014

Published in: Proceedings of the National Academy of Sciences (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Convex programming (90C25) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17) Combinatorial complexity of geometric structures (52C45)

Related Items (7)

Parameterized complexity of configuration integer programs ⋮ Integer programming in parameterized complexity: five miniatures ⋮ Stokes, Gibbs, and volume computation of semi-algebraic sets ⋮ Integer Programming in Parameterized Complexity: Three Miniatures. ⋮ Quantitative geometry ⋮ On the rational polytopes with Chvátal rank 1 ⋮ An FPTAS for the volume of some \(\mathcal{V} \)-polytopes -- it is hard to compute the volume of the intersection of two cross-polytopes

Cites Work

• The difference body of a convex body
• On convex perturbations with a bounded isotropic constant
• A geometric inequality and the complexity of computing volume
• Projections onto Hilbertian subspaces of Banach spaces
• Simulated annealing in convex bodies and an \(O^{*}(n^{4}\)) volume algorithm
• Ellipsoids defined by Banach ideal norms
• A random polynomial-time algorithm for approximating the volume of convex bodies
• Random walks and anO*(n5) volume algorithm for convex bodies

This page was built for publication: Near-optimal deterministic algorithms for volume computation via M-ellipsoids