Centerpoints: A link between optimization and convex geometry

Basu A, Oertel T (2017)

Publication Type: Journal article

Publication year: 2017


Book Volume: 27

Pages Range: 866-889

Journal Issue: 2

DOI: 10.1137/16M1092908


We introduce a concept that generalizes several different notions of a "centerpoint" 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 "best possible" 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.

Authors with CRIS profile

Involved external institutions

How to cite


Basu, A., & Oertel, T. (2017). Centerpoints: A link between optimization and convex geometry. SIAM Journal on Optimization, 27(2), 866-889.


Basu, Amitabh, and Timm Oertel. "Centerpoints: A link between optimization and convex geometry." SIAM Journal on Optimization 27.2 (2017): 866-889.

BibTeX: Download