CAREER: From Dynamic Algorithms to Fast Optimization and Back

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

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.