The Arrangement Method for Linear Programming

COMPUTER SCIENCE/DISCRETE MATH I
Topic:The Arrangement Method for Linear Programming
Speaker:Vladlen Koltun
Affiliation:Stanford University
Date:Monday, April 3
Time/Room:11:15am - 12:15pm/S-101

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.