{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:38:56Z","timestamp":1787337536386,"version":"3.56.0"},"reference-count":21,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CMMI1452820"],"award-info":[{"award-number":["CMMI1452820"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>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&gt; 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 &gt; n$ versus $i \\leq n$. The tools introduced for proving such results are of independent interest for studying intersection cuts.<\/jats:p>","DOI":"10.1137\/17m1128939","type":"journal-article","created":{"date-parts":[[2018,3,27]],"date-time":"2018-03-27T12:45:59Z","timestamp":1522154759000},"page":"904-929","source":"Crossref","is-referenced-by-count":4,"title":["Approximation of Corner Polyhedra with Families of Intersection Cuts"],"prefix":"10.1137","volume":"28","author":[{"given":"Gennadiy","family":"Averkov","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Amitabh","family":"Basu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Joseph","family":"Paat","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,3,27]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"K. Andersen, Q. Louveaux, R. Weismantel, and L. Wolsey,\n                      Inequalities from two rows of a simplex tableau\n                      , in Integer Programming and Combinatorial Optimization, Proceedings of the 12th International IPCO Conference, Ithaca, NY, 2007, M. Fischetti and D. Williamson, eds., Lecture Notes in Comput. Sci. 4513, Springer, Berlin, Heidelberg, 2007, pp. 1-15.","DOI":"10.1007\/978-3-540-72792-7_1"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/080744360"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1007\/s13366-012-0092-8"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2016.0836"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1110.0510"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-014-0775-z"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1287\/moor.24.3.728"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"A. Barvinok,\n                      A Course in Convexity\n                      , AMS, Providence, RI, 2002.","DOI":"10.1090\/gsm\/054"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-009-0281-x"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1100.0461"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1137\/090756375"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0890-5"},{"key":"atypb13","first-page":"123","author":"Conforti M.","year":"2013","journal-title":"Heidelberg"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"M. Conforti, G. Cornue\u0301jols, and G. Zambelli,\n                      Integer Programming\n                      , Grad. Texts in Math. 271, Springer, Cham, 2014.","DOI":"10.1007\/978-3-319-11008-0"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"S. S. Dey and L. A. Wolsey,\n                      Lifting integer variables in minimal inequalities corresponding to lattice-free triangles\n                      , in Integer Programming and Combinatorial Optimization, Proceedings of the 13th International Conference, IPCO 2008, Bertinoro, Italy, 2008, A. Lodi, A. Panconesi, and G. Rinaldi, eds., Lecture Notes in Comput. Sci. 5035, Springer, Berlin, Heidelberg, 2008, pp. 463-475.","DOI":"10.1007\/978-3-540-68891-4_32"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(69)90017-2"},{"key":"atypb17","first-page":"177","author":"Lova\u0301sz L.","year":"1989","journal-title":"Mathematical Programming Society"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585518"},{"key":"atypb19","unstructured":"R. T. Rockafellar,\n                      Convex Analysis\n                      , Princeton University Press, Princeton, NJ, 1970."},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"R. Schneider,\n                      Convex Bodies: The Brunn-Minkowski Theory\n                      , Cambridge University Press, Cambridge, UK, 2014.","DOI":"10.1017\/CBO9781139003858"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2008.09.005"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1128939","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:16:00Z","timestamp":1787336160000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1128939"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M1128939"],"URL":"https:\/\/doi.org\/10.1137\/17m1128939","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}