TY - GEN A1 - Averkov, Gennadiy A1 - Wagner, Christian T1 - Inequalities for the lattice width of lattice-free convex sets in the plane T2 - Beiträge zur Algebra und Geometrie N2 - A closed, convex set K in R2 with non-empty interior is called lattice-free if the interior of K is disjoint with Z2. In this paper we study the relation between the area and the lattice width of a planar lattice-free convex set in the general and centrally symmetric case. A correspondence between lattice width on the one hand and covering minima on the other, allows us to reformulate our results in terms of covering minima introduced by Kannan and Lovász (Ann Math (2) 128(3):577–602, 1988). We obtain a sharp upper bound for the area for any given value of the lattice width. The lattice-free convex sets satisfying the upper bound are characterized. Lower bounds are studied as well. Parts of our results are applied in Averkov et al. (Maximal lattice-free polyhedra: finiteness and an explicit description in dimension three, http://arxiv.org/abs/1010.1077, 2010) for cutting plane generation in mixed integer linear optimization, which was the original inducement for this paper. We further rectify a result of Kannan and Lovász (Ann Math (2) 128(3):577–602, 1988) with a new proof. KW - Area Convex set KW - Covering minimum KW - Inhomogeneous minimum KW - Lattice-free body KW - Lattice width Y1 - 2012 UR - https://link.springer.com/article/10.1007%2Fs13366-011-0028-8 U6 - https://doi.org/10.1007/s13366-011-0028-8 SN - 2191-0383 SN - 0138-4821 VL - 53 IS - 1 SP - 1 EP - 23 ER - TY - GEN A1 - Averkov, Gennadiy T1 - A proof of Lovászs theorem on maximal lattice-free sets T2 - Beiträge zur Algebra und Geometrie N2 - Let K be a maximal lattice-free set in Rd , that is, K is convex and closed subset of Rd , the interior of K does not contain points of Zd and K is inclusion-maximal with respect to the above properties. A result of Lovász asserts that if K is d-dimensional, then K is a polyhedron with at most 2 d facets, and the recession cone of K is a linear space spanned by vectors from Zd . A first complete proof of mentioned Lovász’s result has been published in a paper of Basu, Conforti, Cornuéjols and Zambelli (where the authors use Dirichlet’s approximation as a tool). The aim of this note is to give another proof of this result. Our proof relies on Minkowki’s first fundamental theorem from the geometry of numbers. We remark that the result of Lovász is relevant in integer and mixed-integer optimization. KW - Cutting plane KW - Lattice-free set KW - Lovász’s theorem Y1 - 2013 UR - https://link.springer.com/article/10.1007%2Fs13366-012-0092-8 U6 - https://doi.org/10.1007/s13366-012-0092-8 SN - 2191-0383 SN - 0138-4821 VL - 54 IS - 1 SP - 105 EP - 109 ER - TY - GEN A1 - Averkov, Gennadiy A1 - Conforti, Michelle A1 - Del Pia, Alberto A1 - Di Summa, Marco A1 - Faenza, Yuri T1 - On the convergence of the affine hull of the Chvátal-Gomory closures T2 - SIAM journal on discrete mathematics N2 - Given an integral polyhedron $P\subseteq\mathbb{R}^n$ and a rational polyhedron $Q\subseteq\mathbb{R}^n$ containing the same integer points as $P$, we investigate how many iterations of the Chvátal--Gomory closure operator have to be performed on $Q$ to obtain a polyhedron contained in the affine hull of $P$. We show that if $P$ contains an integer point in its relative interior, then such a number of iterations can be bounded by a function depending only on $n$. On the other hand, we prove that if $P$ is not full-dimensional and does not contain any integer point in its relative interior, then no finite bound on the number of iterations exists. KW - affine hul KW - Chvátal–Gomory closure KW - Chvátal rank KW - cutting plane KW - integral polyhe-dron Y1 - 2013 UR - https://epubs.siam.org/doi/10.1137/120898371 U6 - https://doi.org/10.1137/120898371 SN - 1095-7146 SN - 0895-4801 VL - 27 IS - 3 SP - 1492 EP - 1502 ER - TY - GEN A1 - Averkov, Gennadiy T1 - On maximal S-free sets and the helly number for the family of S-convex sets T2 - SIAM journal on discrete mathematics N2 - We study two combinatorial parameters, which we denote by f(S) and h(S), associated with an arbitrary set S ⊆ Rd, where d ∈ N. In the nondegenerate situation, f(S) is the largest possible number of facets of a d-dimensional polyhedron L such that the interior of L is disjoint with S and L is inclusion-maximal with respect to this property. The parameter h(S) is the Helly number of the family of all sets that can be given as the intersection of S with a convex subset of Rd. We obtain the inequality f(S) ≤ h(S) for an arbitrary S, and the equality f(S) = h(S) for every discrete S. Furthermore, motivated by research in integer and mixed-integer optimization, we show that 2d is the sharp upper bound on f(S) in the case S = (Zd × Rn) ∩ C, where n ≥ 0 and C ⊆ Rd+n is convex. The presented material generalizes and unifies results of various authors, including the result h(Zd) = 2d of Doignon, the related result f(Zd) = 2d of Lov´asz, and the inequality f(Zd ∩ C) ≤ 2d, which has recently been proved for every convex set C ⊆ Rd by Mor´an and Dey. KW - cutting plane KW - Doignon’s theorem KW - Helly’s theorem KW - Helly number KW - intersection cut KW - lattice-free set KW - S-convex set KW - S-free set Y1 - 2013 UR - https://epubs.siam.org/doi/10.1137/110850463 U6 - https://doi.org/10.1137/110850463 SN - 0895-4801 SN - 1095-7146 VL - 27 IS - 3 SP - 1610 EP - 1624 ER - TY - GEN A1 - Averkov, Gennadiy T1 - Constructive Proofs of some Positivstellensätze for Compact Semialgebraic Subsets of R d T2 - Journal of optimization theory and applications N2 - In a broad sense, positivstellensätze are results about representations of polynomials, strictly positive on a given set. We give proofs of some known positivstellensätze for compact semialgebraic subsets of ℝ d , which are to a large extent constructive and elementary. The presented proofs extend and simplify arguments of Berr, Wörmann (Manuscripta Math. 104(2):135–143, 2001) and Schweighofer (J. Pure Appl. Algebra 166(3):307–319, 2002; SIAM J. Optim. 15(3):805–825, 2005). KW - Polytope KW - Positivstellensatz KW - Preordering KW - Semiring KW - Quadratic module Y1 - 2013 UR - https://link.springer.com/article/10.1007%2Fs10957-012-0261-9 U6 - https://doi.org/10.1007/s10957-012-0261-9 SN - 1573-2878 SN - 0022-3239 VL - 158 IS - 2 SP - 410 EP - 418 ER - TY - CHAP A1 - Averkov, Gennadiy A1 - Basu, Amitabh ED - Lee, John ED - Vygen, Jens T1 - On the unique-lifting property T2 - Integer Programming and Combinatorial Optimization N2 - We study the uniqueness of minimal liftings of cut generating functions obtained from maximal lattice-free polytopes. We prove a basic invariance property of unique minimal liftings for general maximal lattice-free polytopes. This generalizes a previous result by Basu, Cornuéjols and Köppe [3] for simplicial maximal lattice-free polytopes, thus completely settling this fundamental question about lifting. We also extend results from [3] for minimal liftings in maximal lattice-free simplices to more general polytopes. These nontrivial generalizations require the use of deep theorems from discrete geometry and geometry of numbers, such as the Venkov-Alexandrov-McMullen theorem on translative tilings, and McMullen’s characterization of zonotopes. KW - Integer Point, Relative Interior, Tile Space, Unimodular Transformation, Nontrivial Generalization Y1 - 2014 SN - 978-3-319-07557-0 SN - 978-3-319-07556-3 U6 - https://doi.org/10.1007/978-3-319-07557-0_7 VL - 2014 SP - 76 EP - 87 PB - Springer ER - TY - GEN A1 - Averkov, Gennadiy A1 - Basu, Amitabh T1 - Lifting properties of maximal lattice-free polyhedra T2 - Mathematical Programming N2 - We study the uniqueness of minimal liftings of cut-generating functions obtained from maximal lattice-free polyhedra. We prove a basic invariance property of unique minimal liftings for general maximal lattice-free polyhedra. This generalizes a previous result by Basu et al. (Math Oper Res 37(2):346–355, 2012) for simplicial maximal lattice-free polytopes, thus completely settling this fundamental question about lifting for maximal lattice-free polyhedra. We further give a very general iterative construction to get maximal lattice-free polyhedra with the unique-lifting property in arbitrary dimensions. This single construction not only obtains all previously known polyhedra with the unique-lifting property, but goes further and vastly expands the known list of such polyhedra. Finally, we extend characterizations from Basu et al. (2012) about lifting with respect to maximal lattice-free simplices to more general polytopes. These nontrivial generalizations rely on a number of results from discrete geometry, including the Venkov-Alexandrov-McMullen theorem on translative tilings and characterizations of zonotopes in terms of central symmetry of their faces. Y1 - 2015 UR - https://link.springer.com/article/10.1007/s10107-015-0865-6 U6 - https://doi.org/10.1007/s10107-015-0865-6 SN - 0025-5610 VL - 154 IS - 1-2 SP - 81 EP - 111 ER - TY - GEN A1 - Averkov, Gennadiy A1 - Krümpelmann, Jan A1 - Nill, Benjamin T1 - Largest integral simplices with one interior integral point - solution of Hensley's conjecture and related results T2 - Advances in Mathematic N2 - For each dimension d, d-dimensional integral simplices with exactly one interior integral point have bounded volume. This was first shown by Hensley. Explicit volume bounds were determined by Hensley, Lagarias and Ziegler, Pikhurko, and Averkov. In this paper we determine the exact upper volume bound for such simplices and characterize the volume-maximizing simplices. We also determine the sharp upper bound on the coefficient of asymmetry of an integral polytope with a single interior integral point. This result confirms a conjecture of Hensley from 1983. Moreover, for an integral simplex with precisely one interior integral point, we give bounds on the volumes of its faces, the barycentric coordinates of the interior integral point and its number of integral points. Furthermore, we prove a bound on the lattice diameter of integral polytopes with a fixed number of interior integral points. The presented results have applications in toric geometry and in integer optimization. Y1 - 2015 UR - https://www.sciencedirect.com/science/article/pii/S0001870815000249?via%3Dihub#! U6 - https://doi.org/10.1016/j.aim.2014.12.035 SN - 0001-8708 VL - Volume 274 SP - 118 EP - 166 ER - TY - GEN A1 - Averkov, Gennadiy A1 - Bianchi, Gabriele T1 - Covariograms generated by valuations T2 - International Mathematics Research Notices N2 - Let ϕ be a real-valued valuation on the family of compact convex subsets of Rn and let K be a convex body in Rn⁠. We introduce the ϕ-covariogram gK,ϕ of K as the function associating to each x∈Rn the value ϕ(K∩(K+x))⁠. If ϕ is the volume, then gK,ϕ is the covariogram, extensively studied in various sources. When ϕ is a quermassintegral (e.g., surface area or mean width) gK,ϕ has been introduced by Nagel [26]. We study various properties of ϕ-covariograms, mostly in the case n=2 and under the assumption that ϕ is translation invariant, monotone, and even. We also consider the generalization of Matheron's covariogram problem to the case of ϕ-covariograms, that is, the problem of determining an unknown convex body K⁠, up to translations and point reflections, by the knowledge of gK,ϕ⁠. A positive solution to this problem is provided under different assumptions, including the case where K is a polygon and ϕ is either strictly monotone or ϕ is the width in a given direction. We prove that there are examples in every dimension n≥3 where K is determined by its covariogram but it is not determined by its width-covariogram. We also present some consequence of this study in stochastic geometry. Y1 - 2015 UR - https://academic.oup.com/imrn/article/2015/19/9277/907311 U6 - https://doi.org/10.1093/imrn/rnu219 SN - 1687-0247 VL - Vol. 2015 IS - 19 SP - 9277 EP - 9329 ER - TY - GEN A1 - Averkov, Gennadiy A1 - González Merino, Bernardo A1 - Henze, Matthias A1 - Paschke, Ingo A1 - Weltge, Stefan T1 - Tight bounds on discrete quantitative Helly numbers T2 - arXiv.org : (math) N2 - Given a subset S of R^n, let c(S,k) be the smallest number t such that whenever finitely many convex sets have exactly k common points in S, there exist at most t of these sets that already have exactly k common points in S. For S = Z^n, this number was introduced by Aliev et al. [2014] who gave an explicit bound showing that c(Z^n,k) = O(k) holds for every fixed n. Recently, Chestnut et al. [2015] improved this to c(Z^n,k) = O(k (log log k)(log k)^{-1/3} ) and provided the lower bound c(Z^n,k) = Omega(k^{(n-1)/(n+1)}). We provide a combinatorial description of c(S,k) in terms of polytopes with vertices in S and use it to improve the previously known bounds as follows: We strengthen the bound of Aliev et al. [2014] by a constant factor and extend it to general discrete sets S. We close the gap for Z^n by showing that c(Z^n,k) = Theta(k^{(n-1)/(n+1)}) holds for every fixed n. Finally, we determine the exact values of c(Z^n,k) for all k <= 4. KW - Metric Geometry KW - Optimization and Control Y1 - 2016 UR - https://arxiv.org/abs/1602.07839 ER - TY - GEN A1 - Averkov, Gennadiy A1 - Krümpelmann, Jan A1 - Weltge, Stefan T1 - Notions of maximality for integral lattice-free polyhedra - the case of dimension three T2 - arXiv.org : (math) N2 - Lattice-free sets (convex subsets of Rd without interior integer points) and their applications for cutting-plane methods in mixed-integer optimization have been studied in recent literature. Notably, the family of all integral lattice-free polyhedra which are not properly contained in another integral lattice-free polyhedron has been of particular interest. We call these polyhedra Zd-maximal. It is known that, for fixed d, the family Zd-maximal integral lattice-free polyhedra is finite up to unimodular equivalence. In view of possible applications in cutting-plane theory, one would like to have a classification of this family. However, this turns out to be a challenging task already for small dimensions. In contrast, the subfamily of all integral lattice-free polyhedra which are not properly contained in any other lattice-free set, which we call Rd-maximal lattice-free polyhedra, allow a rather simple geometric characterization. Hence, the question was raised for which dimensions the notions of Zd-maximality and Rd-maximality are equivalent. This was known to be the case for dimensions one and two. On the other hand, Nill and Ziegler (2011) showed that for dimension d≥4, there exist polyhedra which are Zd-maximal but not Rd-maximal. In this article, we consider the remaining case d=3 and prove that for integral polyhedra the notions of R3-maximality and Z3-maximality are equivalent. As a consequence, the classification of all R3-maximal integral polyhedra by Averkov, Wagner and Weismantel (2011) contains all Z3-maximal integral polyhedra. Y1 - 2015 UR - https://arxiv.org/abs/1509.05200 ER - TY - GEN A1 - Averkov, Gennadiy A1 - Kaibel, Volker A1 - Weltge, Stefan T1 - Maximum semidefinite and linear extension complexity of families of polytopes T2 - arXiv.org : (math) Y1 - 2016 UR - https://arxiv.org/abs/1605.08538 SP - 11 ER - TY - GEN A1 - Averkov, Gennadiy A1 - Langfeld, Barbara T1 - Homometry and direct-sum decompositions of lattice-convex sets T2 - Discrete & computational geometry : an international journal of mathematics and computer science N2 - Two sets in Rd are called homometric if they have the same covariogram, where the covariogram of a finite subset K of Rd is the function associating to each u∈Rd the cardinality of K∩(K+u). Understanding the structure of homometric sets is important for a number of areas of mathematics and applications. If two sets are homometric but do not coincide up to translations and point reflections, we call them nontrivially homometric. We study nontrivially homometric pairs of lattice-convex sets, where a set K is called lattice-convex with respect to a lattice M⊆Rd if K is the intersection of M and a convex subset of Rd. This line of research was initiated in 2005 by Daurat, Gérard and Nivat and, independently, by Gardner, Gronchi and Zong. All pairs of nontrivially homometric lattice-convex sets that have been known so far can essentially be written as direct sums S⊕T and S⊕(−T), where T is lattice-convex, the underlying lattice M is the direct sum of T and some sublattice L, and S is a subset of L. We study pairs of nontrivially homometric lattice-convex sets assuming this particular form and establish a necessary and a sufficient condition for the lattice-convexity of S⊕T. This allows us to explicitly describe all nontrivially homometric pairs in dimension two, under the above assumption, and to construct examples of nontrivially homometric pairs of lattice-convex sets for each d≥3. KW - Covariogram problem KW - Diffraction KW - Discrete tomography KW - Direct sum KW - Homometric sets KW - Lattice-convex set Y1 - 2016 UR - https://link.springer.com/article/10.1007%2Fs00454-016-9786-2 U6 - https://doi.org/10.1007/s00454-016-9786-2 SN - 1432-0444 SN - 0179-5376 VL - 56 IS - 1 SP - 216 EP - 249 ER - TY - GEN A1 - Henk, Martin A1 - Averkov, Gennadiy T1 - Three-Dimensional Polyhedra Can Be Described by Three Polynomial Inequalities T2 - Discrete & computational geometry N2 - Bosse et al. conjectured that for every natural number d≥2 and every d-dimensional polytope P in ℝ d , there exist d polynomials p 1(x),…,p d (x) satisfying P={x∈ℝ d :p 1(x)≥0,…,p d (x)≥0}. We show that every three-dimensional polyhedron can be described by three polynomial inequalities, which confirms the conjecture for the case d=3 but also provides an analogous statement for the case of unbounded polyhedra. The proof of our result is constructive. KW - Łojasiewicz’s inequality KW - Polynomial KW - Polytope KW - Semi-algebraic set KW - Theorem of Bröcker and Scheiderer Y1 - 2009 UR - https://link.springer.com/article/10.1007%2Fs00454-009-9183-1 U6 - https://doi.org/10.1007/s00454-009-9183-1 SN - 1432-0444 VL - 42 IS - 2 SP - 166 EP - 186 ER - TY - GEN A1 - Averkov, Gennadiy T1 - On nearly equilateral simplices and nearly l 8 spaces T2 - Canadian mathematical bulletin Y1 - 2010 U6 - https://doi.org/10.4153/CMB-2010-055-1 SN - 1496-4287 SN - 0008-4395 VL - 53 IS - 3 SP - 394 EP - 397 ER - TY - GEN A1 - Averkov, Gennadiy A1 - Henk, Martin T1 - Representing simple d-dimensional polytopes by d polynomials T2 - Mathematical programming / A N2 - A polynomial representation of a convex d-polytope P is a finite set {p 1(x), . . . , p n (x)} of polynomials over Rd such that P={x∈Rd:pi(x)≥0 for every 1≤i≤n}. Let s(d, P) be the least possible n as above. It is conjectured that s(d, P) = d for all convex d-polytopes P. We confirm this conjecture for simple d-polytopes by providing an explicit construction of d polynomials that represent a given simple d-polytope P. KW - Elementary symmetric polynomial KW - H-representation KW - Real algebraic geometry KW - Semi-algebraic set KW - Theorem of Scheiderer and Bröcker Y1 - 2011 U6 - https://doi.org/10.1007/s10107-009-0280-y SN - 1436-4646 VL - 126 IS - 2 SP - 203 EP - 230 ER - TY - GEN A1 - Averkov, Gennadiy A1 - Bey, Christian T1 - Description of polygonal regions by polynomials of bounded degree T2 - Monatshefte für Mathematik N2 - We show that every (possibly unbounded) convex polygon P in R2 with m edges can be represented by inequalities p 1 ≥ 0, . . ., p n ≥ 0, where the p i ’s are products of at most k affine functions each vanishing on an edge of P and n = n(m, k) satisfies s(m,k)≤n(m,k)≤(1+εm)s(m,k) with s(m,k) ≔ max {m/k, log2 m} and εm→0 as m→∞. This choice of n is asymptotically best possible. An analogous result on representing the interior of P in the form p 1 > 0, . . ., p n > 0 is also given. For k ≤ m/log2 m these statements remain valid for representations with arbitrary polynomials of degree not exceeding k. KW - Gray code KW - Polygon KW - Polynomial KW - Semi-algebraic set KW - Theorem of Bröcker and Scheiderer Y1 - 2011 U6 - https://doi.org/10.1007/s00605-010-0224-x SN - 1436-5081 VL - 162 IS - 1 SP - 19 EP - 27 ER - TY - GEN A1 - Averkov, Gennadiy A1 - Weismantel, R. T1 - Transversal numbers over subsets of linear spaces T2 - Advances in geometry Y1 - 2012 U6 - https://doi.org/10.1515/advgeom.2011.028 SN - 1615-7168 SN - 1615-715X VL - 12 IS - 1 SP - 19 EP - 28 ER - TY - GEN A1 - Averkov, Gennadiy T1 - On the size of lattice simplices with a single interior lattice point T2 - SIAM journal on discrete mathematics N2 - Let $\mathcal{T}^d$ be the set of all d-dimensional simplices T in $\mathbb{R}^d$ with integer vertices and a single integer point in the interior of T. It follows from a result of Hensley that $\mathcal{T}^d$ is finite up to affine transformations that preserve $\mathbb{Z}^d$. It is known that when d grows, the maximum volume of the simplices $T \in \mathcal{T}^d$ becomes extremely large. We improve and refine bounds on the size of $T \in \mathcal{T}^d$ (where by the size we mean the volume or the number of lattice points). It is shown that each $T \in \mathcal{T}^d$ can be decomposed into an ascending chain of faces $G_1 \subseteq \cdots \subseteq G_d=T$ such that for every $i \in \{1,\ldots,d\}$, $G_i$ is i-dimensional and the size of $G_i$ is bounded from above in terms of i and d. The bound on the size of $G_i$ is double exponential in i. The presented upper bounds are asymptotically tight on the log-log scale. Y1 - 2012 UR - https://epubs.siam.org/doi/10.1137/110829052 U6 - https://doi.org/10.1137/110829052 SN - 1095-7146 VL - 26 IS - 2 SP - 515 EP - 526 ER - TY - GEN A1 - Averkov, Gennadiy A1 - Langfeld, Barbara T1 - On the Reconstruction of Planar Lattice-Convex Sets from the Covariogram T2 - Discrete & computational geometry N2 - 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é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. KW - Covariogram KW - Crystallography KW - Diffraction KW - Direct sum KW - Homometric sets KW - Lattice-convex set KW - Matheron’s problem KW - Partial digest problem KW - Quasicrystal KW - Tomography KW - X-ray Y1 - 2012 UR - https://link.springer.com/article/10.1007%2Fs00454-012-9416-6 U6 - https://doi.org/10.1007/s00454-012-9416-6 SN - 1432-0444 VL - 48 IS - 1 SP - 216 EP - 238 ER - TY - GEN A1 - Averkov, Gennadiy T1 - On finitely generated closures in the theory of cutting planes T2 - Discrete optimization KW - Chvátal–Gomory closure KW - Cutting plane KW - Max-facet-width KW - Mixed-integer optimization KW - Split closure Y1 - 2012 UR - https://www.sciencedirect.com/science/article/pii/S1572528612000436?via%3Dihub U6 - https://doi.org/10.1016/j.disopt.2012.06.003 SN - 1572-5286 VL - 9 IS - 4 SP - 209 EP - 215 ER - 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 - 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 - 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 -