Linear Programming and Arrangements

Dr. Koltun is from the University of California, Berkeley
We present a new approach to designing a strongly polynomial algorithm for linear programming. We show that linear programming on any polytope can be reduced to linear programming on an arrangement polytope. This opens up the possibility of designing a simplex-like strongly polynomial algorithm without resolving the Hirsch conjecture. We show that simple deterministic approaches cannot succeed even on arrangement polytopes, and describe initial results towards a randomized solution.

We also present near-optimal solutions to long standing open problems in computational geometry, including the decomposition of arrangements of surfaces, robot motion planning with translations and rotations in three dimensions, complexity of Voronoi diagrams in three dimensions, and more.

Vladlen Koltun is a post-doctoral researcher at University of California, Berkeley, working with Christos Papadimitriou, Umesh Vazirani, Richard Karp, and Ken Goldberg. His doctoral dissertation, completed under the supervision of Micha Sharir, introduced faster algorithms for fundamental problems in computational geometry. Dr. Koltun is the recipient of the Rothschild postdoctoral fellowship and the Machtey award.