On approximation by projections of polytopes with few facets

We provide an affirmative answer to a problem posed by Barvinok and Veomett in [4] , showing that in general an n -dimensional convex body cannot be approximated by a projection of a section of a simplex of subexponential dimension. Moreover, we prove that for all 1 ≤ n ≤ N there exists an n -dimens...

Full description

Saved in:
Bibliographic Details
Published in:Israel journal of mathematics 2014-10, Vol.203 (1), p.141-160
Main Authors: Litvak, Alexander E., Rudelson, Mark, Tomczak-Jaegermann, Nicole
Format: Article
Language:English
Subjects:
Algebra
Analysis
Applications of Mathematics
Group Theory and Generalizations
Mathematical and Computational Physics
Mathematics
Mathematics and Statistics
Theoretical
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We provide an affirmative answer to a problem posed by Barvinok and Veomett in [4] , showing that in general an n -dimensional convex body cannot be approximated by a projection of a section of a simplex of subexponential dimension. Moreover, we prove that for all 1 ≤ n ≤ N there exists an n -dimensional convex body B such that for every n -dimensional convex body K obtained as a projection of a section of an N -dimensional simplex one has , where d (·, ·) denotes the Banach-Mazur distance and c is an absolute positive constant. The result is sharp up to a logarithmic factor.
ISSN:0021-2172
1565-8511
DOI:10.1007/s11856-014-0017-3