Computer Science/Discrete Mathematics Seminar I

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.