CAREER: From Dynamic Algorithms to Fast Optimization and Back

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

Linear programs are fundamental optimization problems used to support decision-making in many fields of society and industry, e.g., airline scheduling, network/traffic congestion management, and efficient manufacturing processing. Beyond static linear optimization problems, this project explores the nascent field of dynamic optimization, where linear programs evolve dynamically due, for example, to parameter evolution or changing underlying environemts. Examples of such dynamic optimization problems include robotic motion, vehicle traffic- and social-networks, and streaming algorithms. Although extensively studied by practitioners, little is known about dynamic linear programs from a theoretical perspective. The objective of this research project is to exploit the synergy between dynamic algorithms and optimization algorithms in order to build a theory for dynamic optimization problems. This will lead to more efficient algorithms and new approaches for addressing linear programs that evolve over time. The comprehensive education plan is designed to build a community of researchers at many levels and includes a summer school for early-stage graduate students and workshops. The research team will also work closely with graduate students on these research topics in order to mentor a new generation of students in theoretical computer science. This project aims to build on synergy between dynamic algorithms and linear programming. Dynamic algorithms maintain solutions while the underlying problem instances changes over time. They serve as essential subroutines to speed up iterative algorithms by efficiently maintaining solutions from one iteration to the next. In addition to being a powerful tool in efficient algorithm design, dynamic algorithms are also especially useful when solving problems that are both naturally dynamic and too large to be recomputed from scratch after each update. Here dynamic graphs and dynamic optimization problems have become more and more prevalent. This project will not only create fast optimization algorithms by developing new dynamic techniques, but also construct fast dynamic algorithms built on top of optimization methods. In essence, this project seeks to transfer techniques from dynamic algorithms to fast optimization and back. Ultimately, the aim is to (i) settle the optimal time complexity of solving linear programs, (ii) develop new dynamic graph algorithms via algebraic and optimization techniques, and (iii) build a theory of dynamic optimization, yielding new algorithmic tools for dynamic linear programs, and understanding the limits and impossibility of solving dynamic linear programs. 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.