@incollection{AverkovBasu, author = {Averkov, Gennadiy and Basu, Amitabh}, title = {On the unique-lifting property}, series = {Integer Programming and Combinatorial Optimization}, volume = {2014}, booktitle = {Integer Programming and Combinatorial Optimization}, editor = {Lee, John and Vygen, Jens}, publisher = {Springer}, isbn = {978-3-319-07557-0}, doi = {10.1007/978-3-319-07557-0_7}, pages = {76 -- 87}, abstract = {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{\´e}jols and K{\"o}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.}, language = {en} } @misc{AverkovBasu, author = {Averkov, Gennadiy and Basu, Amitabh}, title = {Lifting properties of maximal lattice-free polyhedra}, series = {Mathematical Programming}, volume = {154}, journal = {Mathematical Programming}, number = {1-2}, issn = {0025-5610}, doi = {10.1007/s10107-015-0865-6}, pages = {81 -- 111}, abstract = {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.}, 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} }