Amitabh, Basu and Oertel, Timm ORCID: https://orcid.org/0000-0001-5720-8978 2016. Centerpoints: a link between optimization and convex geometry. Presented at: IPCO 2016: International Conference on Integer Programming and Combinatorial Optimization, Liege, Belgium, 1-3 June 2016. Published in: Louveaux, Quentin and Skutella, Martin eds. Integer Programming and Combinatorial Optimization: 18th International Conference, IPCO 2016, Liège, Belgium, June 1-3, 2016, Proceedings. Lecture Notes in Computer Science: Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science , vol.9682 Springer, pp. 14-25. 10.1007/978-3-319-33461-5 |
Preview |
PDF
- Accepted Post-Print Version
Download (222kB) | Preview |
Official URL: http://dx.doi.org/10.1007/978-3-319-33461-5_2
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.
Item Type: | Conference or Workshop Item (Paper) |
---|---|
Date Type: | Published Online |
Status: | Published |
Schools: | Mathematics |
Publisher: | Springer |
ISBN: | 9783319334608 |
ISSN: | 0302-9743 |
Date of First Compliant Deposit: | 30 June 2016 |
Date of Acceptance: | 31 March 2016 |
Last Modified: | 07 Nov 2023 06:40 |
URI: | https://orca.cardiff.ac.uk/id/eprint/92247 |
Actions (repository staff only)
Edit Item |