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

这个项目将试图改进最近在线性规划领域的突破。线性规划是优化的中心工具，用于物流、工厂计划、航班调度和许多其他任务。最近，理论上的计算机科学家已经开发出了线性规划的算法，其性能被证明比以前所知的更好。这些算法依赖于对基本数学对象的新理解，例如向量和其长度的测量，以及函数在这些向量上的行为；例如，在航班调度问题中，向量可以对应于从特定机场计划起飞的航班数量。该项目将关键地让研究生参与设计被证明更好的算法，并将为本科生提供实施算法的机会。PI一直与本科生合作，考虑到它可能产生实际影响，这个项目特别适合纳入本科生。伯克利计算机科学学院现在招收了近900名来自文学与科学学院的学生(除了工程学院的学生外)，其中女性所占比例要大得多。PI对这一群体的研究特别感兴趣。这个项目致力于提高线性规划的复杂性并简化最近的线性规划算法，特别是最大流问题。线性规划问题是在空间中寻找一个点的问题，该点在坐标上使线性函数最优化，并且服从线性不等式。最大流问题是一种特殊的线性规划问题，其中一个人希望在网络中推动尽可能多的流。改进的思想是找到网络的替代表示，在最大流问题的情况下，或者在线性规划的情况下，找到可行向量集，其中传统的优化方法收敛得更快。这些方法结合了基于微积分的最小化方法和有效地捕获网络和多面体的属性的方法。

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.