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