AF: Small: Algorithms March on through Continuous and Combinatorial Methods
AF:小:算法通过连续和组合方法前进
基本信息
- 批准号:1816861
- 负责人:
- 金额:$ 50万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:2018
- 资助国家:美国
- 起止时间:2018-06-01 至 2022-05-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
This project will continue the exploration of the combination of continuous and combinatorial methods for algorithm design. Continuous methods are similar to high school calculus, where the notion of the derivative of a function is used to find exact, optimal solutions to problems such as the shortest way to swim across a moving creek. An example of a combinatorial method is multiplication, where one follows a simple step-by-step method (algorithm) to compute a product. In optimization, both techniques have been used to compute the optimal solutions for many problems. One such example is airline scheduling, which combines aspects of staff scheduling, route planning, and even profit maximization. Recently, a breakthrough in optimization has combined these approaches at a lower level. Combinatorial problems (e.g., scheduling staff) are translated to continuous ones (e.g., multi-variable real number function optimization). Combinatorial structure is re-imposed, based on understanding of the original problem, to speed up calculus-based methods. This has led to remarkable breakthroughs in producing theoretically fast algorithms for basic problems such as the solution of linear systems. Such algorithms are applicable, for example, in climate modelling, weather predictions, and oil exploration. The technique is also making exciting inroads into the area of linear programming, which is used, for example, in the previously mentioned application of airline scheduling.In this project, the idea of "pre-conditioning" a function is studied to allow for continuous ("calculus-based") optimization techniques to run faster. One example is producing an interpolation of a function on a line. The value of the function is specified at particular points, and one wishes to produce the "smoothest" interpolation on the many points on the line. This can be viewed as a multi-variable problem where the value of each point is a variable, but one loses the structure of the line. Re-incorporating this structure into the multi-variable optimization techniques produces very fast algorithms. This simple intuition has been applied to more complicated situations, ranging to very general problems in convex optimization, and is yielding fruit. This project will attempt to further understand and extend the applicability of these techniques.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.
本项目将继续探索连续与组合方法相结合的算法设计。连续方法类似于高中微积分,其中函数导数的概念用于找到问题的精确、最优解决方案,例如游过移动小溪的最短路线。组合方法的一个例子是乘法,其中遵循一种简单的逐步方法(算法)来计算乘积。在优化中,这两种技术都被用来计算许多问题的最佳解决方案。航空公司调度就是这样的一个例子,它结合了员工调度、航线规划甚至利润最大化的各个方面。最近,优化方面的突破在较低水平上结合了这些方法。组合问题(例如,调度人员)被转换为连续问题(例如,多变量实数函数优化)。基于对原始问题的理解,重新施加组合结构,以加速基于微积分的方法。这使得在解决线性系统等基本问题的理论上快速算法方面取得了显着的突破。此类算法适用于气候建模、天气预报和石油勘探等领域。该技术还在线性规划领域取得了令人兴奋的进展,例如,在前面提到的航空公司调度应用中使用了线性规划。在这个项目中,研究了“预处理”函数的思想,以允许连续(“基于微积分”)优化技术运行得更快。一个例子是在一条线上生成函数的插值。函数的值是在特定点指定的,并且人们希望在线上的许多点上产生“最平滑”的插值。这可以看作是一个多变量问题,其中每个点的值都是一个变量,但失去了线的结构。将这种结构重新结合到多变量优化技术中可以产生非常快的算法。这种简单的直觉已应用于更复杂的情况,包括凸优化中非常普遍的问题,并且正在取得成果。该项目将尝试进一步理解和扩展这些技术的适用性。该奖项反映了 NSF 的法定使命,并通过使用基金会的智力价值和更广泛的影响审查标准进行评估,被认为值得支持。
项目成果
期刊论文数量(8)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
A Hoeffding Inequality for Finite State Markov Chains and its Applications to Markovian Bandits
有限状态马尔可夫链的Hoeffding不等式及其在马尔可夫强盗中的应用
- DOI:10.1109/isit44484.2020.9173931
- 发表时间:2020-06
- 期刊:
- 影响因子:0
- 作者:Moulos; Vrettos
- 通讯作者:Vrettos
High-Dimensional Expanders from Expanders
来自 Expanders 的高维扩展器
- DOI:10.4230/lipics.itcs.2020.12
- 发表时间:2020-01
- 期刊:
- 影响因子:0
- 作者:Liu, Siqui;Mohanty, Sidhanth;Yang, Elizabeth
- 通讯作者:Yang, Elizabeth
Universal Algorithms for Clustering
通用聚类算法
- DOI:
- 发表时间:2021-04
- 期刊:
- 影响因子:0
- 作者:Bruce Maggs; Arun Ganesh
- 通讯作者:Arun Ganesh
Robust Algorithms for TSP and Steiner Tree
TSP 和 Steiner 树的稳健算法
- DOI:10.4230/lipics.wabi.2020.17
- 发表时间:2020-01
- 期刊:
- 影响因子:0
- 作者:Ganesh, Arun;Maggs, Bruce;Panigrahi, Debmalya
- 通讯作者:Panigrahi, Debmalya
Privately Answering Counting Queries with Generalized Gaussian Mechanisms
使用广义高斯机制私下回答计数查询
- DOI:10.4230/lipics.forc.2021.1
- 发表时间:2021-07
- 期刊:
- 影响因子:0
- 作者:Ganesh, Arun;Zhao, Jiazheng
- 通讯作者:Zhao, Jiazheng
{{
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 }}
Satish Rao其他文献
A rigorous analysis of population stratification with limited data
用有限的数据对人口分层进行严格分析
- DOI:
- 发表时间:
2007-01-07 - 期刊:
- 影响因子:0
- 作者:
Kamalika Chaudhuri;E. Halperin;Satish Rao;Shuheng Zhou - 通讯作者:
Shuheng Zhou
What Would Edmonds Do? Augmenting Paths and Witnesses for Degree-Bounded MSTs
埃德蒙兹会做什么?
- DOI:
10.1007/s00453-007-9115-5 - 发表时间:
2009-05-22 - 期刊:
- 影响因子:1.1
- 作者:
Kamalika Chaudhuri;Satish Rao;Samantha J. Riesenfeld;Kunal Talwar - 通讯作者:
Kunal Talwar
Molecular characterization and clinical significance of extraintestinal pathogenic Escherichia coli recovered from a south Indian tertiary care hospital.
从印度南部三级护理医院回收的肠外致病性大肠杆菌的分子特征和临床意义。
- DOI:
10.1016/j.micpath.2016.03.001 - 发表时间:
2016-06-01 - 期刊:
- 影响因子:3.8
- 作者:
Arindam Chakraborty;P. Adhikari;S. Shenoy;Satish Rao;B. Dhanashree;V. Saralaya - 通讯作者:
V. Saralaya
Using Max Cut to Enhance Rooted Trees Consistency
使用 Max Cut 增强有根树的一致性
- DOI:
10.1109/tcbb.2006.58 - 发表时间:
2006-10-01 - 期刊:
- 影响因子:0
- 作者:
S. Snir;Satish Rao - 通讯作者:
Satish Rao
The k-traveling repairman problem
k-旅行修理工问题
- DOI:
- 发表时间:
2003-01-12 - 期刊:
- 影响因子:0
- 作者:
Jittat Fakcharoenphol;Chris Harrelson;Satish Rao - 通讯作者:
Satish Rao
Satish Rao的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Satish Rao', 18)}}的其他基金
AF: Small: Algorithms: approximate, combinatorial, and continuous.
AF:小:算法:近似、组合和连续。
- 批准号:
1528174 - 财政年份:2015
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
AitF: Full: Collaborative Research: Graph-theoretic algorithms to improve phylogenomic analyses
AitF:完整:协作研究:改进系统发育分析的图论算法
- 批准号:
1535989 - 财政年份:2015
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
AF: Small: Algorithms: Linear, Spectral, and Approximation.
AF:小:算法:线性、谱和近似。
- 批准号:
1118083 - 财政年份:2011
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
III: Medium: Collaborative Research: Geometric Network Analysis Tools: Algorithmic Methods for Identifying Structure in Large Informatics Graphs
III:媒介:协作研究:几何网络分析工具:识别大型信息学图中结构的算法方法
- 批准号:
0963904 - 财政年份:2010
- 资助金额:
$ 50万 - 项目类别:
Continuing Grant
Collaborative Research: Spectral Graph Theory and Its Applications
合作研究:谱图理论及其应用
- 批准号:
0635357 - 财政年份:2007
- 资助金额:
$ 50万 - 项目类别:
Continuing Grant
Metric embeddings, approximation and combinatorial algorithms.
度量嵌入、近似和组合算法。
- 批准号:
0515304 - 财政年份:2005
- 资助金额:
$ 50万 - 项目类别:
Continuing Grant
Information Technology Research (ITR): Building the Tree of Life -- A National Resource for Phyloinformatics and Computational Phylogenetics
信息技术研究(ITR):构建生命之树——系统信息学和计算系统发育学的国家资源
- 批准号:
0331494 - 财政年份:2003
- 资助金额:
$ 50万 - 项目类别:
Cooperative Agreement
Network Algorithms: Scheduling and Routing
网络算法:调度和路由
- 批准号:
0105533 - 财政年份:2001
- 资助金额:
$ 50万 - 项目类别:
Continuing Grant
相似国自然基金
员工算法规避行为的内涵结构、量表开发及多层次影响机制:基于大(小)数据研究方法整合视角
- 批准号:72372021
- 批准年份:2023
- 资助金额:40 万元
- 项目类别:面上项目
基于球面约束和小波框架正则化的磁共振图像处理变分模型与快速算法
- 批准号:12301545
- 批准年份:2023
- 资助金额:30 万元
- 项目类别:青年科学基金项目
基于谱图小波变换算法的2型糖尿病肠道微生物组学网络标志物筛选研究
- 批准号:
- 批准年份:2022
- 资助金额:30 万元
- 项目类别:青年科学基金项目
用于非小细胞肺癌免疫疗效预测的复合传感模式电子鼻构建及智能算法研究
- 批准号:
- 批准年份:2021
- 资助金额:57 万元
- 项目类别:面上项目
基于相关关系信息增强的遥感图像小目标快速检测算法研究
- 批准号:
- 批准年份:2021
- 资助金额:30 万元
- 项目类别:青年科学基金项目
相似海外基金
Collaborative Research: AF: Small: Structural Graph Algorithms via General Frameworks
合作研究:AF:小型:通过通用框架的结构图算法
- 批准号:
2347321 - 财政年份:2024
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
AF: Small: Communication-Aware Algorithms for Dynamic Allocation of Heterogeneous Resources
AF:小型:用于异构资源动态分配的通信感知算法
- 批准号:
2335187 - 财政年份:2024
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: Structural Graph Algorithms via General Frameworks
合作研究:AF:小型:通过通用框架的结构图算法
- 批准号:
2347322 - 财政年份:2024
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
AF:RI:Small: Fairness in allocation and machine learning problems: algorithms and solution concepts
AF:RI:Small:分配公平性和机器学习问题:算法和解决方案概念
- 批准号:
2334461 - 财政年份:2024
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
AF: Small: New Challenges and Approaches in Clustering Algorithms
AF:小:聚类算法的新挑战和方法
- 批准号:
2311397 - 财政年份:2023
- 资助金额:
$ 50万 - 项目类别:
Standard Grant