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 -