Centerpoints: A Link Between Optimization and Convex Geometry

Amitabh Basu, JHU Dept of Applied Mathematics and Statistics
Host: Michael Dinitz

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.

Speaker Biography

Amitabh Basu is an assistant professor in the Dept. of Applied Mathematics and Statistics at Johns Hopkins University since 2013. He was a visiting assistant professor in the Dept. of Mathematics at University of California, Davis, from 2010-2013. He obtained his Ph.D. in 2010 from Carnegie Mellon University with a thesis on mixed-integer optimization. He received an M.S. in Computer Science from Stony Brook University in 2006, and a bachelor’s in Computer Science from Indian Institute of Technology, Delhi in 2004.

Amitabh Basu is the recipient of the NSF CAREER award in 2015. He was one of the three finalists for the A.W. Tucker Prize 2012 awarded by the Mathematical Optimization Society. Basu serves as an Associate Editor for the journals Mathematics of Operations Research and Discrete Optimization. He also currently serves as Vice Chair for the Integer and Discrete Optimization cluster within the INFORMS Optimization Society.