TY - CHAP A1 - Averkov, Gennadiy A1 - Basu, Amitabh A1 - Paat, Joseph T1 - Approximation of Corner Polyhedra with Families of Intersection Cuts T2 - Integer Programming and Combinatorial Optimization N2 - We study the problem of approximating the corner polyhedron using intersection cuts derived from families of lattice-free sets. In particular, we look at the problem of characterizing families that approximate the corner polyhedron up to a constant factor in fixed dimension n (the constant depends on n). The literature already contains several results in this direction. In this paper, we use the maximum number of facets of a lattice-free set in a family as a measure of its complexity and precisely characterize the level of complexity of a family required for constant factor approximations. As one of the main results, we show that for each natural number n, a corner polyhedron for n integer variables is approximated by intersection cuts from lattice-free sets with at most i facets up to a constant factor (depending only on n) if i>2n−1 and that no such approximation is possible if i≤2n−1. When the approximation factor is allowed to depend on the denominator of the underlying fractional point of the corner polyhedron, we show that the threshold is i>n versus i≤n. The tools introduced for proving such results are of independent interest for studying intersection cuts. KW - Relative Strength Gauge Function Constant Factor Approximation Recession Cone Standard Basis Vector Y1 - 2017 UR - https://link.springer.com/chapter/10.1007%2F978-3-319-59250-3_5 SN - 978-3-319-59249-7 SN - 978-3-319-59250-3 U6 - https://doi.org/10.1007/978-3-319-59250-3_5 SP - 51 EP - 62 PB - Springer Nature Switzerland AG. Part of Springer Nature. CY - Schweiz 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 - Averkov, Gennadiy T1 - Maximum semidefinite and linear extension complexity of families of polytopes T2 - Mathematical Programming N2 - We relate the maximum semidefinite and linear extension complexity of a family of polytopes to the cardinality of this family and the minimum pairwise Hausdorff distance of its members. This result directly implies a known lower bound on the maximum semidefinite extension complexity of 0/1-polytopes. We further show how our result can be used to improve on the corresponding bounds known for polygons with integer vertices. Our geometric proof builds upon nothing else than a simple well-known property of maximum volume inscribed ellipsoids of convex bodies. In particular, it does not rely on factorizations over the semidefinite cone and thus avoids involved procedures of balancing them as required, e.g., in Briët et al. (Math Program 153(1):179–199, 2015). Moreover, we show that the linear extension complexity of every d-dimensional 0/1-polytope is bounded from above by O(2dd). KW - Semidefinite extended formulations Extension complexity Polytopes Y1 - 2018 UR - https://link.springer.com/article/10.1007%2Fs10107-017-1134-7 U6 - https://doi.org/10.1007/s10107-017-1134-7 SN - 0025-5610 SN - 1436-4646 VL - 167 IS - 2 SP - 381 EP - 394 ER - TY - GEN A1 - Averkov, Gennadiy T1 - Lattice simplices with a fixed positive number of interior lattice points: A nearly optimal volume bound T2 - International mathematics research notices: IMRN - Oxford: Oxford University Press, 2018 N2 - We give an explicit upper bound on the volume of lattice simplices with fixed positive number of interior lattice points. The bound differs from the conjectural sharp upper bound only by a linear factor in the dimension. This improves significantly upon the previously best results by Pikhurko from 2001. KW - Combinatorics, Algebraic Geometry, Metric Geometry, Optimization and Control Y1 - 2018 UR - https://arxiv.org/abs/1710.08646 U6 - https://doi.org/10.1093/imrn/rny130 ER - TY - GEN A1 - Averkov, Gennadiy T1 - Approximation of Corner Polyhedra with Families of Intersection Cuts T2 - SIAM Journal on Optimization N2 - We study the problem of approximating the corner polyhedron using intersection cuts derived from families of lattice-free sets in $\mathbb{R}^n$. In particular, we look at the problem of characterizing families that approximate the corner polyhedron up to a constant factor, which depends only on $n$ and not the data or dimension of the corner polyhedron. The literature already contains several results in this direction. In this paper, we use the maximum number of facets of lattice-free sets in a family as a measure of its complexity and precisely characterize the level of complexity of a family required for constant factor approximations. As one of the main results, we show that, for each natural number $n$, a corner polyhedron with $n$ basic integer variables and an arbitrary number of continuous nonbasic variables is approximated up to a constant factor by intersection cuts from lattice-free sets with at most $i$ facets if $i> 2^{n-1}$ and that no such approximation is possible if $i \le 2^{n-1}$. When the approximation factor is allowed to depend on the denominator of the fractional vertex of the linear relaxation of the corner polyhedron, we show that the threshold is $i > n$ versus $i \leq n$. The tools introduced for proving such results are of independent interest for studying intersection cuts. Y1 - 2018 UR - https://epubs.siam.org/doi/10.1137/17M1128939 U6 - https://doi.org/10.1137/17M1128939 VL - 28 IS - 1 SP - 904 EP - 929 ER - TY - GEN A1 - Beisegel, Jesse A1 - Denkert, Carolin A1 - Köhler, Ekkehard A1 - Krnc, Matjaž A1 - Pivač, Nevena A1 - Scheffler, Robert A1 - Strehler, Martin T1 - On the End-Vertex Problem of Graph Searches T2 - Discrete Mathematics & Theoretical Computer Science Y1 - 2019 SN - 1365-8050 SN - 1462-7264 VL - 21 IS - 1 ER - TY - GEN A1 - Beisegel, Jesse A1 - Denkert, Carolin A1 - Köhler, Ekkehard A1 - Krnc, Matjaž A1 - Pivač, Nevena A1 - Scheffler, Robert A1 - Strehler, Martin ED - Coutinho, Gabriel ED - Kohayakawa, Yoshiharu ED - dos Santos, Vinicius ED - Urrutia, Sebastián T1 - Recognizing Graph Search Trees T2 - The proceedings of Lagos 2019, the tenth Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS 2019) 2-7 June 2019, Belo Horizonte, Brazil Y1 - 2019 U6 - https://doi.org/10.1016/j.entcs.2019.08.010 SN - 1571-0661 SP - 99 EP - 110 PB - Elsevier ER - TY - GEN A1 - Beisegel, Jesse A1 - Chudnovsky, Maria A1 - Gurvich, Vladimir A1 - Milanič, Martin A1 - Servatius, Mary ED - Friggstad, Zachary ED - Sack, Jörg-Rüdiger ED - Salavatipour, Mohammad T1 - Avoidable Vertices and Edges in Graphs T2 - Algorithms and Data Structures : 16th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5–7, 2019, Proceedings Y1 - 2019 SN - 978-3-030-24765-2 SN - 978-3-030-24766-9 U6 - https://doi.org/10.1007/978-3-030-24766-9_10 SN - 0302-9743 SN - 1611-3349 SP - 126 EP - 139 PB - Springer CY - Cham ER - TY - GEN A1 - Schlipf, Jon A1 - Fischer, Inga Anita T1 - Rigorous coupled-wave analysis of a multi-layered plasmonic integrated refractive index sensor T2 - Optics Express Y1 - 2021 U6 - https://doi.org/10.1364/OE.438585 SN - 1094-4087 VL - Vol. 29 IS - 22 SP - 36201 EP - 36210 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 - Hofscheier, Johannes A1 - Nill, Benjamin T1 - Generalized flatness constants, spanning lattice polytopes, and the Gromov width T2 - Manuscripta mathematica N2 - In this paper we motivate some new directions of research regarding the lattice width of convex bodies. We show that convex bodies of sufficiently large width contain a unimodular copy of a standard simplex. Following an argument of Eisenbrand and Shmonin, we prove that every lattice polytope contains a minimal generating set of the affine lattice spanned by its lattice points such that the number of generators (and the lattice width of their convex hull) is bounded by a constant which only depends on the dimension. We also discuss relations to recent results on spanning lattice polytopes and how our results could be viewed as the beginning of the study of generalized flatness constants. Regarding symplectic geometry, we point out how the lattice width of a Delzant polytope is related to upper and lower bounds on the Gromov width of its associated symplectic toric manifold. Throughout, we include several open questions. KW - Lattice polytopes KW - Spanning lattice polytopes KW - Lattice width KW - Flatness constant KW - Gromov width KW - Symplectic toric manifolds Y1 - 2023 U6 - https://doi.org/10.1007/s00229-021-01363-x SN - 0025-2611 SN - 1432-1785 VL - 170 IS - 1-2 SP - 147 EP - 165 ER - TY - GEN A1 - Averkov, Gennadiy A1 - Borger, Christopher A1 - Soprunov, Ivan T1 - Classification of Triples of Lattice Polytopes with a Given Mixed Volume T2 - Discrete & Computational Geometry N2 - We present an algorithm for the classification of triples of lattice polytopes with a given mixed volume m in dimension 3. It is known that the classification can be reduced to the enumeration of so-called irreducible triples, the number of which is finite for fixed m. Following this algorithm, we enumerate all irreducible triples of normalized mixed volume up to 4 that are inclusion-maximal. This produces a classification of generic trivariate sparse polynomial systems with up to 4 solutions in the complex torus, up to monomial changes of variables. By a recent result of Esterov, this leads to a description of all generic trivariate sparse polynomial systems that are solvable by radicals. KW - Bernstein–Khovanskii–Kouchnirenko theorem KW - Classification KW - Lattice polytope KW - Mixed volume KW - Newton polytope KW - Sparse polynomial systems Y1 - 2021 U6 - https://doi.org/10.1007/s00454-020-00246-4 SN - 0179-5376 SN - 1432-0444 VL - 66 IS - 1 SP - 165 EP - 202 ER - TY - GEN A1 - Averkov, Gennadiy A1 - Borger, Christopher A1 - Soprunov, Ivan T1 - Inequalities between mixed volumes of convex bodies: volume bounds for the Minkowski sum T2 - Mathematika N2 - In the course of classifying generic sparse polynomial systems which are solvable in radicals, Esterov recently showed that the volume of the Minkowski sum P1+⋯+Pd of d‐dimensional lattice polytopes is bounded from above by a function of order O(m2d), where m is the mixed volume of the tuple (P1,⋯,Pd). This is a consequence of the well‐known Aleksandrov–Fenchel inequality. Esterov also posed the problem of determining a sharper bound. We show how additional relations between mixed volumes can be employed to improve the bound to O(md), which is asymptotically sharp. We furthermore prove a sharp exact upper bound in dimensions 2 and 3. Our results generalize to tuples of arbitrary convex bodies with volume at least one. This paper relies extensively on colour figures. Some references to colour may not be meaningful in the printed version, and we refer the reader to the online version which includes the colour figures. KW - 14M25 KW - 52A39 KW - 52A40 KW - 52B20 (primary) Y1 - 2020 U6 - https://doi.org/10.1112/mtk.12055 VL - 66 IS - 4 SP - 1003 EP - 1027 ER - TY - GEN A1 - Gardill, Markus A1 - Pearson, Dominik A1 - Scharnagl, Julian A1 - Schilling, Klaus T1 - Towards Wireless Ranging and Synchronization Using CubeSat Software-Defined Radio Subsystems T2 - IEEE Space Hardware and Radio Conference, 22-25 January 2023, Las Vegas (NV, USA) Y1 - 2023 SN - 978-1-6654-9315-4 SN - 978-1-6654-9316-1 U6 - https://doi.org/10.1109/SHaRC56958.2023.10046143 SP - 16 EP - 19 PB - IEEE ER - TY - GEN A1 - Averkov, Gennadiy A1 - Soprunov, Ivan T1 - Plücker-type inequalities for mixed areas and intersection numbers of curve arrangements T2 - International Mathematics Research Notices Y1 - 2023 U6 - https://doi.org/10.1093/imrn/rnac216 SN - 1073-7928 IS - 18 SP - 16015 EP - 16050 ER - TY - GEN A1 - Aprile, Manuel A1 - Averkov, Gennadiy A1 - Di Summa, Marco A1 - Hojny, Christopher T1 - The role of rationality in integer-programming relaxations T2 - Mathematical Programming, Series A Y1 - 2023 U6 - https://doi.org/10.1007/s10107-023-01994-w SN - 1436-4646 VL - 205(2024) SP - 745 EP - 771 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 - TY - GEN A1 - Averkov, Gennadiy A1 - Scheiderer, Claus T1 - Convex hulls of monomial curves, and a sparse positivstellensatz T2 - Mathematical Programming : Series B N2 - Consider the closed convex hull K of a monomial curve given parametrically as $$(t^{m_1},\ldots ,t^{m_n})$$ , with the parameter t varying in an interval I. We show, using constructive arguments, that K admits a lifted semidefinite description by $$\mathcal {O}(d)$$ linear matrix inequalities (LMIs), each of size $$\left\lfloor \frac{n}{2} \right\rfloor +1$$ , where $$d= \max \{m_1,\ldots ,m_n\}$$ is the degree of the curve. On the dual side, we show that if a univariate polynomial p(t) of degree d with at most $$2k+1$$ monomials is non-negative on $${\mathbb {R}}_+$$ , then p admits a representation $$p = t^0 \sigma _0 + \cdots + t^{d-k} \sigma _{d-k}$$ , where the polynomials $$\sigma _0,\ldots ,\sigma _{d-k}$$ are sums of squares and $$\deg (\sigma _i) \le 2k$$ . The latter is a univariate positivstellensatz for sparse polynomials, with non-negativity of p being certified by sos polynomials whose degree only depends on the sparsity of p. Our results fit into the general attempt of formulating polynomial optimization problems as semidefinite problems with LMIs of small size. Such small-size descriptions are much more tractable from a computational viewpoint. Y1 - 2024 U6 - https://doi.org/10.1007/s10107-024-02060-9 SN - 0025-5610 PB - Springer Science and Business Media LLC ER - 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 -