AF: Small: Algorithms: approximate, combinatorial, and continuous.

University Of California-Berkeley, Berkeley CA

Investigators

Abstract

This project will attempt to improve recent breakthroughs in the area of linear programming. Linear programming is a central tool for optimization that is used in logistics, factory planning, flight scheduling, and numerous other tasks. Recently, theorical computer scientists have developed algorithms for linear programming with provably better performance than previously known. These algorithms rely on new understanding of basic mathematical objects such as vectors and measures of their length, and the behavior of functions on such vectors; the vectors could correspond, for example, to how many flights are scheduled to leave from a particular airport in a flight scheduling problem. The project will critically involve graduate students in designing provably better algorithms and will provide for opportunities for undergraduates in implementing the algorithms. The PI has consistently worked with undergraduates and this project, given its possibilities for practical impact, is especially well suited for the inclusion of undergraduate students. Berkeley Computer Science now enrolls almost 900 students from the College of Letters and Science (in addition to its College of Engineering Students) which contains a much larger fraction of women. The PI is especially interested in involving this population in research. This project endeavors to improve the complexity and simplify recent algorithms for linear programming and, in particular, the maximum flow problem. The linear programming problem is the problem of finding a point in space that optimizes a linear function on the coordinates and obeys linear inequalities. The maximum flow problem is a particular linear programming problem where one wishes to push as much flow through a network as possible. The idea of the improvement is to find alternate representations of the networks, in the case of the maximum flow problem, or the set of feasible vectors, in the case of linear programming, where traditional optimization methods converge faster. The methods combine a calculus based minimization approach with methods for efficiently capturing properties of networks and polytopes.