AF: Small: Algorithms March on through Continuous and Combinatorial Methods

点击翻译按钮获取中文摘要

This project will continue the exploration of the combination of continuous and combinatorial methods for algorithm design. Continuous methods are similar to high school calculus, where the notion of the derivative of a function is used to find exact, optimal solutions to problems such as the shortest way to swim across a moving creek. An example of a combinatorial method is multiplication, where one follows a simple step-by-step method (algorithm) to compute a product. In optimization, both techniques have been used to compute the optimal solutions for many problems. One such example is airline scheduling, which combines aspects of staff scheduling, route planning, and even profit maximization. Recently, a breakthrough in optimization has combined these approaches at a lower level. Combinatorial problems (e.g., scheduling staff) are translated to continuous ones (e.g., multi-variable real number function optimization). Combinatorial structure is re-imposed, based on understanding of the original problem, to speed up calculus-based methods. This has led to remarkable breakthroughs in producing theoretically fast algorithms for basic problems such as the solution of linear systems. Such algorithms are applicable, for example, in climate modelling, weather predictions, and oil exploration. The technique is also making exciting inroads into the area of linear programming, which is used, for example, in the previously mentioned application of airline scheduling.In this project, the idea of "pre-conditioning" a function is studied to allow for continuous ("calculus-based") optimization techniques to run faster. One example is producing an interpolation of a function on a line. The value of the function is specified at particular points, and one wishes to produce the "smoothest" interpolation on the many points on the line. This can be viewed as a multi-variable problem where the value of each point is a variable, but one loses the structure of the line. Re-incorporating this structure into the multi-variable optimization techniques produces very fast algorithms. This simple intuition has been applied to more complicated situations, ranging to very general problems in convex optimization, and is yielding fruit. This project will attempt to further understand and extend the applicability of these techniques.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.