Page 143 - 8th European Congress of Mathematics ∙ 20-26 June 2021 ∙ Portorož, Slovenia ∙ Book of Abstracts
P. 143
VEX BODIES - APPROXIMATION AND SECTIONS (MS-61)
for Lattice Programming:
• Given some convex body K ⊆ Rn, how many convex bodies Qi are required to cover
K so that, when scaled around their respective centroids by a factor of 2, these convex
bodies are contained inside (1 + ) · K? This question was first considered by Eisenbrand
et al. in the context of Integer Programming for K = B∞n . In that case, a simple dyadic
decomposition along the facets reveals that O(1 + log(1/ ))n convex bodies suffice. For
general p norm balls, exploiting the modulus of smoothness, O(1 + 1/ )n/min(p,2) convex
bodies suffice. This is tight for the Euclidean ball, but it is wide open whether for general
K (even for the cross-polytope) there is an improvement over O(1 + 1/ )n.
• Let K be some convex body and let E be some ellipsoid enclosing K. We consider the
translative covering number N (E , K) but with a twist: For > 0, is there siosm√encBon2ns, tathnet
C > 0 so that N (E, C · K) < 2 n? When K = B∞n and the ellipsoid
√annswBe2nr is yes, i.e. for any > 0, we can scale the cube by some constant and cover
by fewer than 2 n translates. Similarly, when K is the p norm ball for p≥ 2 and
the ellipsoid is an adequately scaled ball, the answer is yes, while for p < 2, the answer
is no (compare the volume).
For both problems I will describe the techniques to obtain these results, briefly sketch their
relevance to Lattice Programming and present some open questions. The talk is based on joint
works with Márton Naszódi and Fritz Eisenbrand respectively.
141
for Lattice Programming:
• Given some convex body K ⊆ Rn, how many convex bodies Qi are required to cover
K so that, when scaled around their respective centroids by a factor of 2, these convex
bodies are contained inside (1 + ) · K? This question was first considered by Eisenbrand
et al. in the context of Integer Programming for K = B∞n . In that case, a simple dyadic
decomposition along the facets reveals that O(1 + log(1/ ))n convex bodies suffice. For
general p norm balls, exploiting the modulus of smoothness, O(1 + 1/ )n/min(p,2) convex
bodies suffice. This is tight for the Euclidean ball, but it is wide open whether for general
K (even for the cross-polytope) there is an improvement over O(1 + 1/ )n.
• Let K be some convex body and let E be some ellipsoid enclosing K. We consider the
translative covering number N (E , K) but with a twist: For > 0, is there siosm√encBon2ns, tathnet
C > 0 so that N (E, C · K) < 2 n? When K = B∞n and the ellipsoid
√annswBe2nr is yes, i.e. for any > 0, we can scale the cube by some constant and cover
by fewer than 2 n translates. Similarly, when K is the p norm ball for p≥ 2 and
the ellipsoid is an adequately scaled ball, the answer is yes, while for p < 2, the answer
is no (compare the volume).
For both problems I will describe the techniques to obtain these results, briefly sketch their
relevance to Lattice Programming and present some open questions. The talk is based on joint
works with Márton Naszódi and Fritz Eisenbrand respectively.
141
