The flatness theorem for nonsymmetric convex bodies via the local theory of Banach spaces

Citation
W. Banaszczyk et al., The flatness theorem for nonsymmetric convex bodies via the local theory of Banach spaces, MATH OPER R, 24(3), 1999, pp. 728-750
Citations number
29
Categorie Soggetti
Mathematics
Journal title
MATHEMATICS OF OPERATIONS RESEARCH
ISSN journal
0364765X → ACNP
Volume
24
Issue
3
Year of publication
1999
Pages
728 - 750
Database
ISI
SICI code
0364-765X(199908)24:3<728:TFTFNC>2.0.ZU;2-4
Abstract
Let L be a lattice in R-n and Ka convex body disjoint from L. The classical Flatness Theorem asserts that then w(K, L), the L-width of K, does not exc eed some bound, depending only on the dimension n; this fact was later foun d relevant to questions in integer programming. Kannan and Lovasz (1988) sh owed that under the above assumptions w(K, L) less than or equal to Cn(2), where C is a universal constant. Banaszczyk (1996) proved that w(K, L) less than or equal to Cn(1 + log n) if K has a centre of symmetry. In the prese nt paper we show that w(K, L) less than or equal to Cn(3/2) for an arbitrar y K. It is conjectured that the exponent 3/2 may be replaced by 1, perhaps at the cost of a logarithmic factor; we prove that for some naturally arisi ng classes of bodies.