Vladlen Koltun
Computer Science Department, Stanford
Thursday, December 1, 2005
1131 Kemper Hall
3 :10-4:00 p.m.
The Arrangement Method for Linear Programming
We propose 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. The graphs of arrangement polytopes have considerably better structure than general polytope graphs, including a small polynomial diameter. This opens up the possibility of designing a simplex-like strongly polynomial linear programming algorithm without resolving the Hirsch conjecture.
Bio
Vladlen Koltun joined the Computer Science Department of Stanford University in 2005 following a three-year postdoctoral appointment at University of California, Berkeley. His doctoral dissertation, completed at Tel Aviv University in 2002 introduced faster algorithms for fundamental problems in computational geometry. Prof. Koltun's work spans geometric computing, algorithm design, and a variety of application areas in computer science and mathematics.