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 - 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 - 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 -