@misc{AverkovLangfeld, author = {Averkov, Gennadiy and Langfeld, Barbara}, title = {On the Reconstruction of Planar Lattice-Convex Sets from the Covariogram}, series = {Discrete \& computational geometry}, volume = {48}, journal = {Discrete \& computational geometry}, number = {1}, issn = {1432-0444}, doi = {10.1007/s00454-012-9416-6}, pages = {216 -- 238}, abstract = {A finite subset K of ℤ d is said to be lattice-convex if K is the intersection of ℤ d with a convex set. The covariogram g K of K⊆ℤ d is the function associating to each u∈ℤ d the cardinality of K∩(K+u). Daurat, G{\´e}rard, and Nivat and independently Gardner, Gronchi, and Zong raised the problem of the reconstruction of lattice-convex sets K from g K . We provide a partial positive answer to this problem by showing that for d=2 and under mild extra assumptions, g K determines K up to translations and reflections. As a complement to the theorem on reconstruction we also extend the known counterexamples (i.e., planar lattice-convex sets which are not reconstructible, up to translations and reflections) to an infinite family of counterexamples.}, language = {en} } @misc{Averkov, author = {Averkov, Gennadiy}, title = {On finitely generated closures in the theory of cutting planes}, series = {Discrete optimization}, volume = {9}, journal = {Discrete optimization}, number = {4}, issn = {1572-5286}, doi = {10.1016/j.disopt.2012.06.003}, pages = {209 -- 215}, language = {en} } @incollection{AverkovBasuPaat, author = {Averkov, Gennadiy and Basu, Amitabh and Paat, Joseph}, title = {Approximation of Corner Polyhedra with Families of Intersection Cuts}, series = {Integer Programming and Combinatorial Optimization}, booktitle = {Integer Programming and Combinatorial Optimization}, publisher = {Springer Nature Switzerland AG. Part of Springer Nature.}, address = {Schweiz}, isbn = {978-3-319-59249-7}, doi = {10.1007/978-3-319-59250-3_5}, pages = {51 -- 62}, abstract = {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.}, language = {en} } @misc{AverkovGonzalezMerinoPaschkeetal., author = {Averkov, Gennadiy and Gonz{\´a}lez Merino, Bernardo and Paschke, Ingo and Schymura, Matthias and Weltge, Stefan}, title = {Tight bounds on discrete quantitative Helly numbers}, series = {Advances in Applied Mathematics}, volume = {89}, journal = {Advances in Applied Mathematics}, issn = {0196-8858}, doi = {10.1016/j.aam.2017.04.003}, pages = {76 -- 101}, language = {en} } @misc{Averkov, author = {Averkov, Gennadiy}, title = {Maximum semidefinite and linear extension complexity of families of polytopes}, series = {Mathematical Programming}, volume = {167}, journal = {Mathematical Programming}, number = {2}, issn = {0025-5610}, doi = {10.1007/s10107-017-1134-7}, pages = {381 -- 394}, abstract = {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{\"e}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).}, language = {en} } @misc{Averkov, author = {Averkov, Gennadiy}, title = {Lattice simplices with a fixed positive number of interior lattice points: A nearly optimal volume bound}, series = {International mathematics research notices: IMRN - Oxford: Oxford University Press, 2018}, journal = {International mathematics research notices: IMRN - Oxford: Oxford University Press, 2018}, doi = {10.1093/imrn/rny130}, pages = {15}, abstract = {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.}, language = {en} } @misc{Averkov, author = {Averkov, Gennadiy}, title = {Approximation of Corner Polyhedra with Families of Intersection Cuts}, series = {SIAM Journal on Optimization}, volume = {28}, journal = {SIAM Journal on Optimization}, number = {1}, doi = {10.1137/17M1128939}, pages = {904 -- 929}, abstract = {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.}, language = {en} } @misc{AverkovHojnySchymura, author = {Averkov, Gennadiy and Hojny, Christopher and Schymura, Matthias}, title = {Computational aspects of relaxation complexity: possibilities and limitations}, series = {Mathematical Programming}, volume = {197}, journal = {Mathematical Programming}, number = {2}, issn = {0025-5610}, doi = {10.1007/s10107-021-01754-8}, pages = {1173 -- 1200}, language = {en} } @misc{AverkovSchymura, author = {Averkov, Gennadiy and Schymura, Matthias}, title = {Complexity of linear relaxations in integer programming}, series = {Mathematical Programming}, volume = {194}, journal = {Mathematical Programming}, number = {1-2}, issn = {0025-5610}, doi = {10.1007/s10107-021-01623-4}, pages = {191 -- 227}, language = {en} } @misc{AverkovHofscheierNill, author = {Averkov, Gennadiy and Hofscheier, Johannes and Nill, Benjamin}, title = {Generalized flatness constants, spanning lattice polytopes, and the Gromov width}, series = {Manuscripta mathematica}, volume = {170}, journal = {Manuscripta mathematica}, number = {1-2}, issn = {0025-2611}, doi = {10.1007/s00229-021-01363-x}, pages = {147 -- 165}, abstract = {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.}, language = {en} } @misc{AverkovBorgerSoprunov, author = {Averkov, Gennadiy and Borger, Christopher and Soprunov, Ivan}, title = {Classification of Triples of Lattice Polytopes with a Given Mixed Volume}, series = {Discrete \& Computational Geometry}, volume = {66}, journal = {Discrete \& Computational Geometry}, number = {1}, issn = {0179-5376}, doi = {10.1007/s00454-020-00246-4}, pages = {165 -- 202}, abstract = {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.}, language = {en} } @misc{AverkovBorgerSoprunov, author = {Averkov, Gennadiy and Borger, Christopher and Soprunov, Ivan}, title = {Inequalities between mixed volumes of convex bodies: volume bounds for the Minkowski sum}, series = {Mathematika}, volume = {66}, journal = {Mathematika}, number = {4}, doi = {10.1112/mtk.12055}, pages = {1003 -- 1027}, abstract = {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.}, language = {en} } @misc{AverkovSoprunov, author = {Averkov, Gennadiy and Soprunov, Ivan}, title = {Pl{\"u}cker-type inequalities for mixed areas and intersection numbers of curve arrangements}, series = {International Mathematics Research Notices}, journal = {International Mathematics Research Notices}, number = {18}, issn = {1073-7928}, doi = {10.1093/imrn/rnac216}, pages = {16015 -- 16050}, language = {en} } @misc{AprileAverkovDiSummaetal., author = {Aprile, Manuel and Averkov, Gennadiy and Di Summa, Marco and Hojny, Christopher}, title = {The role of rationality in integer-programming relaxations}, series = {Mathematical Programming, Series A}, volume = {205(2024)}, journal = {Mathematical Programming, Series A}, issn = {1436-4646}, doi = {10.1007/s10107-023-01994-w}, pages = {745 -- 771}, language = {en} } @misc{AverkovSchymura, author = {Averkov, Gennadiy and Schymura, Matthias}, title = {On the maximal number of columns of a Delta-modular integer matrix: bounds and computations}, series = {Mathematical Programming, Series B}, volume = {2023}, journal = {Mathematical Programming, Series B}, issn = {1436-4646}, doi = {10.1007/s10107-023-01964-2}, pages = {29}, language = {en} } @misc{AverkovHojnySchymura, author = {Averkov, Gennadiy and Hojny, Christopher and Schymura, Matthias}, title = {Efficient MIP techniques for computing relaxation complexity}, series = {Mathematical Programming Computation}, volume = {15}, journal = {Mathematical Programming Computation}, number = {3}, issn = {1867-2957}, doi = {10.1007/s12532-023-00241-9}, pages = {549 -- 580}, language = {en} } @misc{AverkovScheiderer, author = {Averkov, Gennadiy and Scheiderer, Claus}, title = {Convex hulls of monomial curves, and a sparse positivstellensatz}, series = {Mathematical Programming : Series B}, journal = {Mathematical Programming : Series B}, publisher = {Springer Science and Business Media LLC}, issn = {0025-5610}, doi = {10.1007/s10107-024-02060-9}, pages = {19}, abstract = {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.}, language = {en} }