CAREER: From Dynamic Algorithms to Fast Optimization and Back

职业：从动态算法到快速优化并返回

• 批准号: 2338816
• 负责人: Jan van den Brand
• 金额: $ 64.98万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2024
• 资助国家: 美国
• 起止时间: 2024-02-01 至 2029-01-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2338816&HistoricalAwards=false
• 关键词: CAREER; Dynamic; Algorithms; Fast; Optimization

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.

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