CAREER: From Dynamic Algorithms to Fast Optimization and Back

线性规划是用于支持社会和工业许多领域决策的基本优化问题，例如，航班调度，网络/交通拥堵管理和高效制造加工。除了静态线性优化问题，该项目还探索了动态优化的新兴领域，其中线性程序动态演变，例如，参数演变或底层环境的变化。此类动态优化问题的例子包括机器人运动、车辆交通和社交网络以及流算法。尽管从业人员对动态线性规划进行了广泛的研究，但从理论角度来看，人们对动态线性规划知之甚少。本研究的目的是利用动态算法与优化算法之间的协同作用，以建立动态优化问题的理论。这将导致更有效的算法和新的方法来处理随时间演变的线性程序。该综合教育计划旨在建立一个多层次的研究人员社区，并包括一个面向早期研究生的暑期学校和讲习班。研究团队还将与研究生在这些研究课题上密切合作，以指导新一代的理论计算机科学学生。这个项目旨在建立动态算法和线性规划之间的协同作用。当底层问题实例随时间变化时，动态算法维护解决方案。它们作为重要的子例程，通过有效地维护从一次迭代到下一次迭代的解决方案来加速迭代算法。除了作为高效算法设计的强大工具之外，动态算法在解决自然动态且每次更新后都无法重新计算的大问题时也特别有用。在这里，动态图和动态优化问题变得越来越普遍。本项目不仅将通过开发新的动态技术创建快速优化算法，而且将在优化方法的基础上构建快速动态算法。从本质上讲，该项目旨在将技术从动态算法转移到快速优化并返回。最终，目标是(i)解决求解线性规划的最优时间复杂度，（ii）通过代数和优化技术开发新的动态图算法，以及（iii）建立动态优化理论，为动态线性规划提供新的算法工具，并理解求解动态线性规划的限制和不可能。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.