Collaborative Research: AF: Medium: Fundamental Challenges in Optimization

合作研究：AF：中：优化中的基本挑战

基本信息

批准号：
2106444
负责人：
Santosh Vempala
金额：
$ 105万
依托单位：
Georgia Tech Research Corporation
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2021
资助国家：
美国
起止时间：
2021-07-01 至 2025-06-30
项目状态：
未结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2106444&HistoricalAwards=false
关键词：
Collaborative Research AF Medium Fundamental

项目摘要

Efficient Optimization is the bedrock of modern computation. Progress over the last century has led to powerful techniques to solve problems from myriad applications. The complexity of basic questions such as solving linear systems, linear programs and integer programs is at the core of the theory of algorithms. The goal of this project is to advance the field by addressing challenging problems on the frontier of efficient optimization. New algorithms for the problems considered would be of direct interest to many disciplines in science and engineering. The project includes a research workshop targeted at junior researchers, as well as a video tutorial course by the team of investigators on contemporary techniques in optimization. Research findings from the project are being incorporated into courses on “Continuous Algorithms”, “Spectral Algorithms” and “Integer and Linear Programming”. Course content and software resulting from the project is being made publicly available.The focus problems of this project range from continuous to discrete: (1) sparse general Linear Systems, (2) sparse Linear Programs and p-norm minimization, (3) using Semi-definite Programs for efficient low-rank approximation to combinatorial optimization problems, (4) advancing the continuous approach to discrete optimization and (5) resolving the complexity of integer programming. Recent progress on discrete optimization has relied heavily on inspiration and analysis from continuous methods, while the solution of continuous optimization problems often uses graph theory. It is anticipated that new techniques bridging this spectrum, and of broad, general applicability, will be developed. The connections to operations research, numerical analysis, stochastic processes (including various types of diffusion), homotopy methods, graph theory, geometric properties of convexity and the theory of lattices are being enhanced.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.

高效优化是现代计算的基石。上个世纪的进步带来了解决无数应用问题的强大技术，解决线性系统、线性规划和整数规划等基本问题的复杂性是理论的核心。该项目的目标是通过解决优化前沿的挑战性问题来推动该领域的发展，所考虑的问题的新算法将引起科学和工程领域许多学科的直接兴趣。初级研究人员以及研究人员团队制作的关于当代优化技术的视频教程课程正在被纳入该项目的“连续算法”、“谱算法”和“整数和线性规划”课程内容和软件中。该项目的重点问题范围从连续到离散：(1) 稀疏一般线性系统，(2) 稀疏线性规划和 p 范数最小化，(3) 使用用于组合优化问题的低秩近似的半定规划，(4) 推进离散优化的连续方法，以及 (5) 解决整数有效规划的复杂性。离散优化的最新进展在很大程度上依赖于连续优化的灵感和分析。方法，而连续优化问题的解决通常使用图论，预计将开发出与运筹学、数值分析、随机过程（包括各种）相关的具有广泛通用性的新技术。扩散类型）、同伦方法、图论、凸性几何性质和晶格理论正在得到加强。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

期刊论文数量（16）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Approximation Algorithms for the Weighted Nash Social Welfare via Convex and Non-Convex Programs

通过凸和非凸规划加权纳什社会福利的近似算法

DOI：
发表时间：
2024-01
期刊：
Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms
影响因子：
0
作者：
Brown, A;Laddha, A;Pittu M;Singh, M.
通讯作者：
Singh, M.

Condition-number-independent convergence rate of Riemannian Hamiltonian Monte Carlo with numerical integrators

具有数值积分器的黎曼哈密顿蒙特卡罗的与条件数无关的收敛速度

DOI：
发表时间：
2023-01
期刊：
Conference on Learning Theory
影响因子：
0
作者：
Kook, Yunbum;Lee, Yin Tat;Shen, Ruoqi;Vempala, Santosh S.
通讯作者：
Vempala, Santosh S.

Maximum Flow and Minimum-Cost Flow in Almost-Linear Time

几乎线性时间内的最大流量和最小成本流量

DOI：
10.1109/focs54457.2022.00064
发表时间：
2022-03-01
期刊：
2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)
影响因子：
0
作者：
L. Chen;Rasmus Kyng;Yang P. Liu;Richard Peng;Maximilian Probst Gutenberg;Sushant Sachdeva
通讯作者：
Sushant Sachdeva

Nested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time

嵌套剖析遇到 IPM：近线性时间内的平面最小成本流

DOI：
10.1137/1.9781611977073.7
发表时间：
2022-01
期刊：
Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA
影响因子：
0
作者：
Dong, Sally;Gao, Yu;Goranci, Gramoz;Lee, Yin Tat;Peng, Richard;Sachdeva, Sushant;Ye Guanghao
通讯作者：
Ye Guanghao

A Simple Framework for Finding Balanced Sparse Cuts via APSP

通过 APSP 寻找平衡稀疏割的简单框架