TY - GEN A1 - Beck, Matthias A1 - Schymura, Matthias T1 - Deep Lattice Points in Zonotopes, Lonely Runners, and Lonely Rabbits T2 - International Mathematics Research Notices Y1 - 2023 U6 - https://doi.org/https://doi.org/10.1093/imrn/rnad232 SN - 1073-7928 VL - 2024 IS - 8 SP - 6553 EP - 6578 PB - Oxford University Press (OUP) ER - TY - GEN A1 - Averkov, Gennadiy A1 - González Merino, Bernardo A1 - Paschke, Ingo A1 - Schymura, Matthias A1 - Weltge, Stefan T1 - Tight bounds on discrete quantitative Helly numbers T2 - Advances in Applied Mathematics Y1 - 2017 UR - https://www.sciencedirect.com/science/article/abs/pii/S019688581730043X U6 - https://doi.org/10.1016/j.aam.2017.04.003 SN - 0196-8858 VL - 89 SP - 76 EP - 101 ER - TY - GEN A1 - Schymura, Matthias A1 - Seidel, Ina A1 - Weltge, Stefan T1 - Lifts for Voronoi cells of lattices T2 - Discrete & Computational Geometry N2 - Many polytopes arising in polyhedral combinatorics are linear projections of higher-dimensional polytopes with significantly fewer facets. Such lifts may yield compressed representations of polytopes, which are typically used to construct small-size linear programs. Motivated by algorithmic implications for the closest vector problem, we study lifts of Voronoi cells of lattices. We construct an explicit d -dimensional lattice such that every lift of the respective Voronoi cell has 2Ω(d/logd)facets. On the positive side, we show that Voronoi cells of d -dimensional root lattices and their dual lattices have lifts with O(d)and O(dlogd)facets, respectively. We obtain similar results for spectrahedral lifts. KW - Lattices KW - Voronoi cells KW - Extended formulations KW - 52B05 KW - 52B12 KW - 90C05 KW - 52C07 KW - Mathematical Sciences Y1 - 2023 U6 - https://doi.org/10.1007/s00454-023-00522-z SN - 0179-5376 SN - 1432-0444 VL - 70 IS - 3 SP - 845 EP - 865 PB - Springer US ER - TY - GEN A1 - Codenotti, Giulia A1 - Santos, Francisco A1 - Schymura, Matthias T1 - The Covering Radius and a Discrete Surface Area for Non-Hollow Simplices T2 - Discrete & Computational Geometry KW - Covering radius KW - Discrete surface area KW - Lattice polytopes Y1 - 2022 U6 - https://doi.org/10.1007/s00454-021-00330-3 SN - 0179-5376 SN - 1432-0444 VL - 67 IS - 1 SP - 65 EP - 111 ER - TY - GEN A1 - Averkov, Gennadiy A1 - Hojny, Christopher A1 - Schymura, Matthias T1 - Computational aspects of relaxation complexity: possibilities and limitations T2 - Mathematical Programming KW - Integer programming formulation KW - Relaxation complexity Y1 - 2023 U6 - https://doi.org/10.1007/s10107-021-01754-8 SN - 0025-5610 SN - 1436-4646 VL - 197 IS - 2 SP - 1173 EP - 1200 ER - TY - GEN A1 - Averkov, Gennadiy A1 - Schymura, Matthias T1 - Complexity of linear relaxations in integer programming T2 - Mathematical Programming Y1 - 2022 U6 - https://doi.org/10.1007/s10107-021-01623-4 SN - 0025-5610 SN - 1436-4646 VL - 194 IS - 1-2 SP - 191 EP - 227 ER - TY - GEN A1 - Averkov, Gennadiy A1 - Schymura, Matthias T1 - On the maximal number of columns of a Delta-modular integer matrix: bounds and computations T2 - Mathematical Programming, Series B Y1 - 2023 U6 - https://doi.org/10.1007/s10107-023-01964-2 SN - 1436-4646 SN - 0025-5610 VL - 2023 ER - TY - GEN A1 - Averkov, Gennadiy A1 - Hojny, Christopher A1 - Schymura, Matthias T1 - Efficient MIP techniques for computing relaxation complexity T2 - Mathematical Programming Computation Y1 - 2023 U6 - https://doi.org/10.1007/s12532-023-00241-9 SN - 1867-2957 SN - 1867-2949 VL - 15 IS - 3 SP - 549 EP - 580 ER - TY - GEN A1 - Henk, Martin A1 - Schymura, Matthias A1 - Xue, Fei T1 - Packing minima and lattice points in convex bodies T2 - Moscow Journal of Combinatorics and Number Theory N2 - Motivated by long-standing conjectures on the discretization of classical inequalities in the geometry of numbers, we investigate a new set of parameters, which we call packing minima, associated to a convex body K and a lattice Λ. These numbers interpolate between the successive minima of K and the inverse of the successive minima of the polar body of K and can be understood as packing counterparts to the covering minima of Kannan & Lovász (1988). As our main results, we prove sharp inequalities that relate the volume and the number of lattice points in K to the sequence of packing minima. Moreover, we extend classical transference bounds and discuss a natural class of examples in detail. Y1 - 2021 U6 - https://doi.org/10.2140/moscow.2021.10.25 SN - 2640-7361 VL - 10 IS - 1 SP - 25 EP - 48 PB - Mathematical Sciences Publishers ER - TY - GEN A1 - Cslovjecsek, Jana A1 - Malikiosis, Romanos Diogenes A1 - Naszódi, Márton A1 - Schymura, Matthias T1 - Computing the Covering Radius of a Polytope with an Application to Lonely Runners T2 - Combinatorica N2 - We study the computational problem of determining the covering radius of a rational polytope. This parameter is defined as the minimal dilation factor that is needed for the lattice translates of the correspondingly dilated polytope to cover the whole space. As our main result, we describe a new algorithm for this problem, which is simpler, more efficient and easier to implement than the only prior algorithm of Kannan (1992). Motivated by a variant of the famous Lonely Runner Conjecture, we use its geometric interpretation in terms of covering radii of zonotopes, and apply our algorithm to prove the first open case of three runners with individual starting points. Y1 - 2022 U6 - https://doi.org/10.1007/s00493-020-4633-8 SN - 0209-9683 VL - 42 IS - 4 SP - 463 EP - 490 PB - Springer Science and Business Media LLC ER -