{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:41:11Z","timestamp":1787341271423,"version":"build-2736575974"},"reference-count":65,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/501100002920","name":"Research Grants Council, University Grants Committee","doi-asserted-by":"publisher","award":["16213219"],"award-info":[{"award-number":["16213219"]}],"id":[{"id":"10.13039\/501100002920","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002920","name":"Research Grants Council, University Grants Committee","doi-asserted-by":"publisher","award":["16214721"],"award-info":[{"award-number":["16214721"]}],"id":[{"id":"10.13039\/501100002920","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ADDS ANR-19-CE48-0005"],"award-info":[{"award-number":["ADDS ANR-19-CE48-0005"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1618866"],"award-info":[{"award-number":["CCF-1618866"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2024,8,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>Coverings of convex bodies have emerged as a central component in the design of efficient solutions to approximation problems involving convex bodies. Intuitively, given a convex body [Formula: see text] and [Formula: see text], a covering is a collection of convex bodies whose union covers [Formula: see text] such that a constant factor expansion of each body lies within an [Formula: see text] expansion of [Formula: see text]. Coverings have been employed in many applications, such as approximations for diameter, width, and [Formula: see text]-kernels of point sets, approximate nearest neighbor searching, polytope approximations with low combinatorial complexity, and approximations to the closest vector problem (CVP). It is known how to construct coverings of size [Formula: see text] for general convex bodies in [Formula: see text]. In special cases, such as when the convex body is the [Formula: see text] unit ball, this bound has been improved to [Formula: see text]. This raises the question of whether such a bound generally holds. In this paper we answer the question in the affirmative. We demonstrate the power and versatility of our coverings by applying them to the problem of approximating a convex body by a polytope, where the error is measured through the Banach\u2013Mazur metric. Given a well-centered convex body [Formula: see text] and an approximation parameter [Formula: see text], we show that there exists a polytope [Formula: see text] consisting of [Formula: see text] vertices (facets) such that [Formula: see text]. This bound is optimal in the worst case up to factors of [Formula: see text]. (This bound has been established recently using different techniques, but our approach is arguably simpler and more elegant.) As an additional consequence, we obtain the fastest [Formula: see text]-approximate CVP algorithm that works in any norm, with a running time of [Formula: see text] up to polynomial factors in the input size, and we obtain the fastest [Formula: see text]-approximation algorithm for integer programming. We also present a framework for constructing coverings of optimal size for any convex body (up to factors of [Formula: see text]).<\/jats:p>","DOI":"10.1137\/23m1568351","type":"journal-article","created":{"date-parts":[[2024,7,31]],"date-time":"2024-07-31T03:49:01Z","timestamp":1722397741000},"page":"1002-1038","source":"Crossref","is-referenced-by-count":2,"title":["Economical Convex Coverings and Applications"],"prefix":"10.1137","volume":"53","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0939-4192","authenticated-orcid":true,"given":"Sunil","family":"Arya","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, The Hong Kong University of Science and Technology, Hong Kong."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Guilherme D.","family":"da Fonseca","sequence":"additional","affiliation":[{"name":"Aix-Marseille Universit\u00e9 and LIS Lab, Marseille, France."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3290-8932","authenticated-orcid":true,"given":"David M.","family":"Mount","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Institute for Advanced Computer Studies, University of Maryland, College Park, MD USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2024,7,31]]},"reference":[{"key":"ref1","unstructured":"A. Abdelkader and D. M. Mount, Economical Delone sets for approximating convex bodies, in Proceedings of the 16th Scandinavian Workshop on Algorithm Theory, LIPIcs. Leibniz Int. Proc. Inform., Wadern, Germany, 2018, 4, https:\/\/doi.org\/10.4230\/LIPIcs.SWAT.2018.4."},{"key":"ref2","doi-asserted-by":"crossref","unstructured":"D. Aggarwal, H. Bennett, A. Golovnev, and N. Stephens-Davidowitz, Fine-grained hardness of CVP(P)-everything that we can prove (and nothing else), in Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadlphia 2021, pp. 1816\u20131835, https:\/\/doi.org\/10.1137\/1.9781611976465.109.","DOI":"10.1137\/1.9781611976465.109"},{"key":"ref3","doi-asserted-by":"crossref","unstructured":"D. Aggarwal, D. Dadush, and N. Stephens-Davidowitz, Solving the closest vector problem in \\(2^n\\) time \u2013 The discrete Gaussian strikes again!, in Proceedings 56th Annual IEEE Symposium on the Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 2015, pp. 563\u2013582, https:\/\/doi.org\/10.1109\/FOCS.2015.41.","DOI":"10.1109\/FOCS.2015.41"},{"key":"ref4","doi-asserted-by":"crossref","unstructured":"M. Ajtai, R. Kumar, and D. Sivakumar, A sieve algorithm for the shortest lattice vector problem, in Proceedings of the 33rd Annual ACM Symposium on the Theory of Computing, ACM, New York, 2001, pp. 601\u2013610, https:\/\/doi.org\/10.1145\/380752.380857.","DOI":"10.1145\/380752.380857"},{"key":"ref5","unstructured":"S. Arora, Probabilistic Checking of Proofs and Hardness of Approximation Problems, Ph.D. thesis, University of California, Berkeley, Berkeley, CA, 1994."},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1145\/3559106"},{"key":"ref7","doi-asserted-by":"crossref","unstructured":"S. Arya, G. D. da Fonseca, and D. M. Mount, Optimal area-sensitive bounds for polytope approximation, in Proceedings of the 28th Annual Symposium on Computational Geometry, ACM, New York, 2012, pp. 363\u2013372, https:\/\/doi.org\/10.1145\/2261250.2261305.","DOI":"10.1145\/2261250.2261305"},{"key":"ref8","doi-asserted-by":"crossref","unstructured":"S. Arya, G. D. da Fonseca, and D. M. Mount, Polytope approximation and the Mahler volume, in Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2012, pp. 29\u201342, https:\/\/doi.org\/10.1137\/1.9781611973099.3.","DOI":"10.1137\/1.9781611973099.3"},{"key":"ref9","unstructured":"S. Arya, G. D. da Fonseca, and D. M. Mount, Near-optimal \\(\\varepsilon\\)-kernel construction and related problems, in Proceedings of the 33rd International Symposium on Computational Geometry, LIPIcs. Leibniz Int. Proc. Inform., Wadern, Germany, 2017, 10, https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2017.10, https:\/\/arxiv.org\/abs\/1703.10868."},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-016-9856-5"},{"key":"ref11","doi-asserted-by":"crossref","unstructured":"S. Arya, G. D. da Fonseca, and D. M. Mount, Optimal approximate polytope membership, in Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2017, pp. 270\u2013288, https:\/\/doi.org\/10.1137\/1.9781611974782.18.","DOI":"10.1137\/1.9781611974782.18"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-009-9140-z"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-012-9412-x"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1006\/aima.1999.1904"},{"key":"ref15","first-page":"21","volume":"65","author":"B\u00e1r\u00e1ny I.","year":"2000","journal-title":"Rend. Circ. Mat. Palermo (2)"},{"key":"ref16","series-title":"Lecture Notes in Math 1892","first-page":"77","volume-title":"Stochastic Geometry","author":"B\u00e1r\u00e1ny I.","year":"2007"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1112\/S0025579300015266"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1093\/imrn\/rnt078"},{"key":"ref19","doi-asserted-by":"crossref","unstructured":"H. Bennett, A. Golovnev, and N. Stephens-Davidowitz, On the quantitative hardness of CVP, in Proceedings of the 58th Annual IEEE Symposium on the Foundations of Computer Science, 2017, pp. 13\u201324, https:\/\/doi.org\/10.1109\/FOCS.2017.11.","DOI":"10.1109\/FOCS.2017.11"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.12.045"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1007\/BF01388911"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1007\/BF02573971"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1007\/BF00967115"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-4383-8"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9834-8"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2016.v012a880"},{"key":"ref27","doi-asserted-by":"crossref","unstructured":"D. Dadush, C. Peikert, and S. Vempala, Enumerative lattice algorithms in any norm via M-ellipsoid coverings, in Proceedings of the 52nd Annual IEEE Symposium on the Foundations of Computer Science, 2011, pp. 580\u2013589, https:\/\/doi.org\/10.1109\/FOCS.2011.31.","DOI":"10.1109\/FOCS.2011.31"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-003-0019-y"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9045(74)90120-8"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-019-00075-0"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1145\/102782.102783"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511566172"},{"key":"ref33","doi-asserted-by":"crossref","unstructured":"F. Eisenbrand, N. H\u00e4hnle, and M. Niemeier, Covering cubes and the closest vector problem, in Proceedings 27th Annual Symposium on Computational Geometry, 2011, pp. 417\u2013423, https:\/\/doi.org\/10.1145\/1998196.1998264.","DOI":"10.1145\/1998196.1998264"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2021.09.006"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1112\/S0025579300002655"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.4171\/rmi\/1263"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-97881-4"},{"key":"ref38","first-page":"281","volume":"5","author":"Gruber P. M.","year":"1993","journal-title":"Forum Math."},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1090\/pspum\/007\/0156259"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-20901-7_10"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1007\/s001459900042"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1287\/moor.12.3.415"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-008-0669-4"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1007\/BF01457454"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1287\/moor.8.4.538"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.2307\/1969800"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1007\/BF01199119"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-98-02162-X"},{"key":"ref49","doi-asserted-by":"publisher","DOI":"10.1137\/100811970"},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1006\/aima.1999.1903"},{"key":"ref51","unstructured":"N. H. Mustafa and S. Ray, Near-optimal generalisations of a theorem of Macbeath, in Proceedings of the 31st International Symposium on Theoretical Aspects of Computer\u00a0Science 25, LIPIcs. Leibniz Int. Proc. Inform., Wadern, Germany, 2014, pp. 578\u2013589, https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2014.578."},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.1353\/ajm.2020.0018"},{"key":"ref53","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-022-00392-x"},{"key":"ref54","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29849-3_20"},{"key":"ref55","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45537-X_24"},{"key":"ref56","first-page":"75","volume-title":"Cryptology and Computational Number Theory, Proc. Sympos. Appl. Math.","author":"Odlyzko A. M.","year":"1990"},{"key":"ref57","doi-asserted-by":"crossref","unstructured":"V. Reis and T. Rothvoss, The subspace flatness conjecture and faster integer programming, in Proceedings of the 64th Annual IEEE Symposium on the Foundations of\u00a0Computer Science, IEEE, Piscataway, NJ, 2023, pp. 974\u2013988, https:\/\/doi.org\/10.1109\/FOCS57990.2023.00060.","DOI":"10.1109\/FOCS57990.2023.00060"},{"key":"ref58","doi-asserted-by":"publisher","DOI":"10.1007\/BF01899997"},{"key":"ref59","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-06901-7_33"},{"key":"ref60","first-page":"155","volume":"8","author":"Santal\u00f3 L. A.","year":"1949","journal-title":"Port. Math."},{"key":"ref61","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511526282"},{"key":"ref62","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-23733-6"},{"key":"ref63","unstructured":"P. van Emde Boas, Another NP-complete Problem and the Complexity of Computing Short Vectors in a Lattice, Tecnical report, Department of Mathmatics, University of Amsterdam, Amsterdam, 1981."},{"key":"ref64","first-page":"573","volume-title":"Combinatorial and Computational Geometry","author":"Vempala S.","year":"2005"},{"key":"ref65","doi-asserted-by":"crossref","unstructured":"C. Vernicos and C. Walsh, Flag-approximability of convex bodies and volume growth of Hilbert geometries, Ann. Sci. \u00c9c. Norm. Sup\u00e9r. (4), 54 (2021), pp. 1297\u20131314, https:\/\/hal.archives-ouvertes.fr\/hal-01423693.","DOI":"10.24033\/asens.2482"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/23M1568351","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:12:06Z","timestamp":1787339526000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/23M1568351"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,31]]},"references-count":65,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,8,31]]}},"alternative-id":["10.1137\/23M1568351"],"URL":"https:\/\/doi.org\/10.1137\/23m1568351","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,7,31]]}}}