{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:36:31Z","timestamp":1787340991197,"version":"3.56.0"},"reference-count":46,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","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":[[2017,1]]},"abstract":"<jats:p>We introduce a concept that generalizes several different notions of a \u201ccenterpoint\u201d in the literature. We develop an oracle-based algorithm for convex mixed-integer optimization based on centerpoints. Further, we show that algorithms based on centerpoints are \u201cbest possible\u201d in a certain sense. Motivated by this, we establish structural results about this concept and provide efficient algorithms for computing these points. Our main motivation is to understand the complexity of oracle-based convex mixed-integer optimization.<\/jats:p>","DOI":"10.1137\/16m1092908","type":"journal-article","created":{"date-parts":[[2017,5,9]],"date-time":"2017-05-09T12:50:56Z","timestamp":1494334256000},"page":"866-889","source":"Crossref","is-referenced-by-count":11,"title":["Centerpoints: A Link between Optimization and Convex Geometry"],"prefix":"10.1137","volume":"27","author":[{"given":"Amitabh","family":"Basu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Timm","family":"Oertel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2017,5,9]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1137\/110850463"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1515\/advgeom.2011.028"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1112\/S0025579312000101"},{"key":"atypb4","first-page":"14","author":"Basu A.","year":"2016","journal-title":"Springer"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"S. Basu, R. Pollack, and M.F. Roy,\n                      On the combinatorial and algebraic complexity of quantifier elimination\n                      , J. ACM (JACM), 43 (1996), pp. 1002-1045.","DOI":"10.1145\/235809.235813"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-006-0074-4"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008733"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1142\/S021819590300127X"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1007\/s11222-008-9054-2"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.2307\/1912699"},{"key":"atypb11","first-page":"430","author":"Chan T. M.","year":"2004","journal-title":"Philadelphia"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2014.0670"},{"key":"atypb13","unstructured":"D. Dadush,\n                      Integer Programming, Lattice Algorithms, and Deterministic Volume Estimation\n                      , Ph.D. thesis, Georgia Institute of Technology, Atlanta, GA, 2012."},{"key":"atypb15","unstructured":"J. De Loera, R. La Haye, D. Oliveros, and E. Rolda\u0301n-Pensado,\n                      Helly Numbers of Algebraic Subsets of $\\mathbb{R}^d$\n                      , preprint, arXiv:1504.00076v2, 2015."},{"key":"atypb16","first-page":"214","author":"Del Pia A.","year":"2016","journal-title":"Springer"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176348890"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/j.csda.2015.12.011"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(88)80005-1"},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"M. Gro\u0308tschel, L. Lova\u0301sz, and A. Schrijver,\n                      Geometric Algorithms and Combinatorial Optimization\n                      , Algorithms Combin. 2, Springer, Berlin, 1988.","DOI":"10.1007\/978-3-642-97881-4"},{"key":"atypb21","unstructured":"P. Gruber,\n                      Convex and Discrete Geometry\n                      , Grundlehren Math. Wiss. 336, Springer, Berlin, 2007."},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1960.10.1257"},{"key":"atypb23","first-page":"233","author":"Grunbaum B.","year":"1963","journal-title":"RI"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2005.04.004"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2012.11.003"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1111\/j.1749-6632.1979.tb32803.x"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1287\/moor.12.3.415"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1007\/BF01442795"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1006\/jmva.2001.2052"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1007\/BF02128669"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1287\/moor.8.4.538"},{"key":"atypb32","doi-asserted-by":"crossref","unstructured":"R. Y. Liu, R. J. Serfling, and D. L. Souvaine,\n                      Data Depth: Robust Multivariate Analysis, Computational Geometry, and Applications\n                      , DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 72, AMS, Providence, RI, 2006.","DOI":"10.1090\/dimacs\/072"},{"key":"atypb33","first-page":"351","author":"Micciancio D.","year":"2010","journal-title":"New York"},{"key":"atypb34","first-page":"17","author":"Mosler K.","year":"2013","journal-title":"Berlin"},{"key":"atypb35","unstructured":"A. Nemirovski and D. Yudin,\n                      Problem Complexity and Method Efficiency in Optimization\n                      , Wiley, Chichester, England, 1983."},{"key":"atypb36","doi-asserted-by":"crossref","unstructured":"Y. Nesterov,\n                      Introductory Lectures on Convex Optimization\n                      , Appl. Optim. 87, Kluwer Academic, Boston, 2004.","DOI":"10.1007\/978-1-4419-8853-9"},{"key":"atypb37","unstructured":"T. Oertel,\n                      Integer Convex Minimization in Low Dimensions\n                      , Ph.D. thesis, Diss., Eidgeno\u0308ssische Technische Hochschule ETH Zu\u0308rich, Zu\u0308rich, 2014."},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2014.07.005"},{"key":"atypb39","first-page":"319","author":"Pak I.","year":"2000","journal-title":"NJ"},{"key":"atypb40","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1007\/PL00020903","volume":"49","author":"Rousseeuw P. J.","year":"1999","journal-title":"Metrika"},{"key":"atypb41","doi-asserted-by":"crossref","unstructured":"M. Talagrand,\n                      Sharper bounds for Gaussian and empirical processes\n                      , Ann. Probab. (1994), pp. 28-76.","DOI":"10.1214\/aop\/1176988847"},{"key":"atypb42","doi-asserted-by":"crossref","unstructured":"G. Toth,\n                      Measures of Symmetry for Convex Sets and Stability\n                      , Springer, Cham, Switzerland, 2015.","DOI":"10.1007\/978-3-319-23733-6"},{"key":"atypb43","first-page":"523","author":"Tukey J. W.","year":"1975","journal-title":"Canada"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1137\/1116025"},{"key":"atypb45","first-page":"42","author":"Vempala S. S.","year":"2010","journal-title":"Germany"},{"key":"atypb46","doi-asserted-by":"crossref","unstructured":"E. Werner,\n                      Floating bodies and illumination bodies\n                      , in Proceedings of the International Conference Integral Geometry and Convexity: Wuhan, China, 18-23 October 2004, World Scientific, Hackensack, NJ, 2006, pp. 129-140.","DOI":"10.1142\/9789812774644_0009"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2016.0781"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/16M1092908","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:59:56Z","timestamp":1787338796000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M1092908"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1]]},"references-count":46,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["10.1137\/16M1092908"],"URL":"https:\/\/doi.org\/10.1137\/16m1092908","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,1]]}}}