When: Monday, April 04, 3:00 p.m.

Where: 3305 Newell-Simon Hall

VLADLEN KOLTUN, University of California, Berkeley

Faculty Candidate Talk

Abstract:
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.

BIO: Vladlen Koltun is a postdoctoral researcher at University of California, Berkeley, working with Christos Papadimitriou, Richard Karp, Umesh Vazirani and Ken Goldberg. His doctoral dissertation, completed under the supervision of Micha Sharir, introduced faster algorithms for fundamental problems in computational geometry. Dr. Koltun's work spans geometric computing, algorithm design, and a variety of application areas in computer science and mathematics. He is the recipient of the Rothschild postdoctoral fellowship and the Machtey award.

HOST: Gary Miller. Contact Charlotte Yano (yano@cs) for appointments.

<< Back