Collaborative Research: AF: Medium: Fundamental Challenges in Optimization
合作研究:AF:中:优化中的基本挑战
基本信息
- 批准号:2105772
- 负责人:
- 金额:$ 14.93万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Continuing Grant
- 财政年份:2021
- 资助国家:美国
- 起止时间:2021-07-01 至 2025-06-30
- 项目状态:未结题
- 来源:
- 关键词:
项目摘要
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的法定使命,并通过使用基金会的知识价值和更广泛的影响审查标准进行评估,被认为值得支持。
项目成果
期刊论文数量(6)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
A nearly-linear time algorithm for linear programs with small treewidth: a multiscale representation of robust central path
- DOI:10.1145/3406325.3451056
- 发表时间:2020-11
- 期刊:
- 影响因子:0
- 作者:Sally Dong;Y. Lee;Guanghao Ye
- 通讯作者:Sally Dong;Y. Lee;Guanghao Ye
A Simple Framework for Finding Balanced Sparse Cuts via APSP
通过 APSP 寻找平衡稀疏割的简单框架
- DOI:
- 发表时间:2023
- 期刊:
- 影响因子:0
- 作者:Chen, Li;Kyng, Rasmus;Probst Gutenberg, Maximilian;Sachdeva, Sushant
- 通讯作者:Sachdeva, Sushant
Determinant Maximization via Matroid Intersection Algorithms
通过拟阵交集算法实现行列式最大化
- DOI:
- 发表时间:2022
- 期刊:
- 影响因子:0
- 作者:Brown, A;Laddha, A.;Pittu, M.;Singh, M.;Tetali, P.
- 通讯作者:Tetali, P.
Nested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time
嵌套剖析与 IPM 的结合:近线性时间内的平面最小成本流
- DOI:10.1137/1.9781611977073.7
- 发表时间:2022
- 期刊:
- 影响因子:0
- 作者:Dong, Sally;Gao, Yu;Goranci, Gramoz;Lee, Yin Tat;Peng, Richard;Sachdeva, Sushant;Ye Guanghao
- 通讯作者:Ye Guanghao
A Unified Approach to Discrepancy Minimization
最小化差异的统一方法
- DOI:
- 发表时间:2022
- 期刊:
- 影响因子:0
- 作者:Bansal, Nikhil;Laddha, Aditi;Vempala, Santosh
- 通讯作者:Vempala, Santosh
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Yin Tat Lee其他文献
Minimum cost flows, MDPs, and ℓ1-regression in nearly linear time for dense instances
密集实例的近线性时间内的最小成本流、MDP 和 ℓ1 回归
- DOI:
- 发表时间:
2021 - 期刊:
- 影响因子:0
- 作者:
Jan van den Brand;Yin Tat Lee;Yang P. Liu;Thatchaphol Saranurak;Aaron Sidford;Zhao Song;Di Wang - 通讯作者:
Di Wang
Yin Tat Lee的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Yin Tat Lee', 18)}}的其他基金
CAREER: The Interplay between Combinatorial Optimization and Algorithmic Convex Geometry
职业:组合优化和算法凸几何之间的相互作用
- 批准号:
1749609 - 财政年份:2018
- 资助金额:
$ 14.93万 - 项目类别:
Continuing Grant
TRIPODS+X: RES: Collaborative Research: Scaling Up Descriptive Epidemiology and Metabolic Network Models via Faster Sampling
TRIPODS X:RES:协作研究:通过更快的采样扩大描述性流行病学和代谢网络模型
- 批准号:
1839116 - 财政年份:2018
- 资助金额:
$ 14.93万 - 项目类别:
Standard Grant
相似国自然基金
Research on Quantum Field Theory without a Lagrangian Description
- 批准号:24ZR1403900
- 批准年份:2024
- 资助金额:0.0 万元
- 项目类别:省市级项目
Cell Research
- 批准号:31224802
- 批准年份:2012
- 资助金额:24.0 万元
- 项目类别:专项基金项目
Cell Research
- 批准号:31024804
- 批准年份:2010
- 资助金额:24.0 万元
- 项目类别:专项基金项目
Cell Research (细胞研究)
- 批准号:30824808
- 批准年份:2008
- 资助金额:24.0 万元
- 项目类别:专项基金项目
Research on the Rapid Growth Mechanism of KDP Crystal
- 批准号:10774081
- 批准年份:2007
- 资助金额:45.0 万元
- 项目类别:面上项目
相似海外基金
Collaborative Research: AF: Medium: The Communication Cost of Distributed Computation
合作研究:AF:媒介:分布式计算的通信成本
- 批准号:
2402836 - 财政年份:2024
- 资助金额:
$ 14.93万 - 项目类别:
Continuing Grant
Collaborative Research: AF: Medium: Foundations of Oblivious Reconfigurable Networks
合作研究:AF:媒介:遗忘可重构网络的基础
- 批准号:
2402851 - 财政年份:2024
- 资助金额:
$ 14.93万 - 项目类别:
Continuing Grant
Collaborative Research: AF: Small: New Directions in Algorithmic Replicability
合作研究:AF:小:算法可复制性的新方向
- 批准号:
2342244 - 财政年份:2024
- 资助金额:
$ 14.93万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: Exploring the Frontiers of Adversarial Robustness
合作研究:AF:小型:探索对抗鲁棒性的前沿
- 批准号:
2335411 - 财政年份:2024
- 资助金额:
$ 14.93万 - 项目类别:
Standard Grant
NSF-BSF: Collaborative Research: AF: Small: Algorithmic Performance through History Independence
NSF-BSF:协作研究:AF:小型:通过历史独立性实现算法性能
- 批准号:
2420942 - 财政年份:2024
- 资助金额:
$ 14.93万 - 项目类别:
Standard Grant
Collaborative Research: AF: Medium: Algorithms Meet Machine Learning: Mitigating Uncertainty in Optimization
协作研究:AF:媒介:算法遇见机器学习:减轻优化中的不确定性
- 批准号:
2422926 - 财政年份:2024
- 资助金额:
$ 14.93万 - 项目类别:
Continuing Grant
Collaborative Research: AF: Small: Structural Graph Algorithms via General Frameworks
合作研究:AF:小型:通过通用框架的结构图算法
- 批准号:
2347322 - 财政年份:2024
- 资助金额:
$ 14.93万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: Real Solutions of Polynomial Systems
合作研究:AF:小:多项式系统的实数解
- 批准号:
2331401 - 财政年份:2024
- 资助金额:
$ 14.93万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: Real Solutions of Polynomial Systems
合作研究:AF:小:多项式系统的实数解
- 批准号:
2331400 - 财政年份:2024
- 资助金额:
$ 14.93万 - 项目类别:
Standard Grant
Collaborative Research: AF: Medium: Fast Combinatorial Algorithms for (Dynamic) Matchings and Shortest Paths
合作研究:AF:中:(动态)匹配和最短路径的快速组合算法
- 批准号:
2402283 - 财政年份:2024
- 资助金额:
$ 14.93万 - 项目类别:
Continuing Grant