Centerpoints: a link between optimization and convex geometry

Basu, Amitabh and Oertel, Timm ORCID: https://orcid.org/0000-0001-5720-8978 2017. Centerpoints: a link between optimization and convex geometry. SIAM Journal on Optimization 27 (2) , pp. 866-889. 10.1137/16M1092908

Preview

PDF - Published Version Download (320kB) | Preview

Abstract

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 several 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.

Item Type:	Article
Date Type:	Published Online
Status:	Published
Schools:	Mathematics
Subjects:	Q Science > QA Mathematics
Uncontrolled Keywords:	convex mixed-integer optimization, centerpoints, convex and discrete geometry
Publisher:	Society for Industrial and Applied Mathematics
ISSN:	1052-6234
Date of First Compliant Deposit:	27 May 2017
Date of Acceptance:	21 March 2017
Last Modified:	04 May 2023 16:18
URI:	https://orca.cardiff.ac.uk/id/eprint/100934

Citation Data

Cited 8 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item