AF: Small: Algorithms: approximate, combinatorial, and continuous.
AF:小:算法:近似、组合和连续。
基本信息
- 批准号:1528174
- 负责人:
- 金额:$ 45万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:2015
- 资助国家:美国
- 起止时间:2015-08-01 至 2018-07-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
This project will attempt to improve recent breakthroughs in the area of linear programming. Linear programming is a central tool for optimization that is used in logistics, factory planning, flight scheduling, and numerous other tasks. Recently, theorical computer scientists have developed algorithms for linear programming with provably better performance than previously known. These algorithms rely on new understanding of basic mathematical objects such as vectors and measures of their length, and the behavior of functions on such vectors; the vectors could correspond, for example, to how many flights are scheduled to leave from a particular airport in a flight scheduling problem. The project will critically involve graduate students in designing provably better algorithms and will provide for opportunities for undergraduates in implementing the algorithms. The PI has consistently worked with undergraduates and this project, given its possibilities for practical impact, is especially well suited for the inclusion of undergraduate students. Berkeley Computer Science now enrolls almost 900 students from the College of Letters and Science (in addition to its College of Engineering Students) which contains a much larger fraction of women. The PI is especially interested in involving this population in research.This project endeavors to improve the complexity and simplify recent algorithms for linear programming and, in particular, the maximum flow problem. The linear programming problem is the problem of finding a point in space that optimizes a linear function on the coordinates and obeys linear inequalities. The maximum flow problem is a particular linear programming problem where one wishes to push as much flow through a network as possible. The idea of the improvement is to find alternate representations of the networks, in the case of the maximum flow problem, or the set of feasible vectors, in the case of linear programming, where traditional optimization methods converge faster. The methods combine a calculus based minimization approach with methods for efficiently capturing properties of networks and polytopes.
该项目将试图改善线性编程领域的最新突破。 线性编程是用于优化的中心工具,用于物流,工厂规划,飞行计划以及许多其他任务。 最近,理论计算机科学家开发了线性编程算法,其性能比以前所知要好。 这些算法依赖于对基本数学对象的新理解,例如向量及其长度的度量以及此类向量上的功能行为。例如,向量可以与计划在飞行计划问题中从特定机场离开多少航班相对应。 该项目将严重涉及研究生设计更好的算法,并为本科生提供实施算法的机会。 PI一直与本科生合作,鉴于其实践影响的可能性,该项目特别适合包括本科生。伯克利计算机科学现在招募了来自文书和科学学院(除其工程学院的学生)的近900名学生,其中包含更大的女性。 PI特别有兴趣让该人群参与研究。这项项目努力提高复杂性并简化了最新的线性编程算法,尤其是最大流量问题。 线性编程问题是在空间中找到一个问题,该问题可以优化坐标上的线性函数并服从线性不等式。最大流量问题是一个特定的线性编程问题,人们希望将尽可能多的流通过网络推动。改进的想法是,在最大流量问题或可行的向量集的情况下,在线性编程的情况下,传统优化方法会更快地收敛。 这些方法将基于微积分的最小化方法与有效捕获网络和多面体属性的方法结合在一起。
项目成果
期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
数据更新时间:{{ journalArticles.updateTime }}
{{
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其他文献
Cytoplasm localized ARID1B promotes oncogenesis in pancreatic cancer by activating RAF-ERK signaling
细胞质定位的 ARID1B 通过激活 RAF-ERK 信号传导促进胰腺癌的肿瘤发生
- DOI:
10.1101/830075 - 发表时间:
2019 - 期刊:
- 影响因子:0
- 作者:
Srinivas Animireddy;Padmavathi Kavadipula;V. Kotapalli;S. Gowrishankar;Satish Rao;M. Bashyam - 通讯作者:
M. Bashyam
Approximating the Solution to Mixed Packing and Covering LPs in parallel Õ ( − 3 ) time
并行 Õ ( − 3 ) 时间近似混合填充和覆盖 LP 的解
- DOI:
- 发表时间:
2016 - 期刊:
- 影响因子:0
- 作者:
Michael W. Mahoney;Satish Rao;Di Wang;Peng Zhang - 通讯作者:
Peng Zhang
Excited states of tetrahedral single-core Si29 nanoparticles
四面体单核Si29纳米粒子的激发态
- DOI:
- 发表时间:
2004 - 期刊:
- 影响因子:0
- 作者:
Satish Rao;Jdb Sutin;R. Clegg;E. Gratton;M. Nayfeh;S. Habbal;Argyrios Tsolakidis;R. Martin - 通讯作者:
R. Martin
An Efficient and Accurate Graph-Based Approach to Detect Population Substructure
一种高效、准确的基于图的群体子结构检测方法
- DOI:
- 发表时间:
2007 - 期刊:
- 影响因子:0
- 作者:
S. Sridhar;Satish Rao;E. Halperin - 通讯作者:
E. Halperin
Localization of Electrical Flows
电流的本地化
- DOI:
10.1137/1.9781611975031.103 - 发表时间:
2017 - 期刊:
- 影响因子:2.3
- 作者:
Aaron Schild;Satish Rao;N. Srivastava - 通讯作者:
N. Srivastava
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 March on through Continuous and Combinatorial Methods
AF:小:算法通过连续和组合方法前进
- 批准号:
1816861 - 财政年份:2018
- 资助金额:
$ 45万 - 项目类别:
Standard Grant
AitF: Full: Collaborative Research: Graph-theoretic algorithms to improve phylogenomic analyses
AitF:完整:协作研究:改进系统发育分析的图论算法
- 批准号:
1535989 - 财政年份:2015
- 资助金额:
$ 45万 - 项目类别:
Standard Grant
AF: Small: Algorithms: Linear, Spectral, and Approximation.
AF:小:算法:线性、谱和近似。
- 批准号:
1118083 - 财政年份:2011
- 资助金额:
$ 45万 - 项目类别:
Standard Grant
III: Medium: Collaborative Research: Geometric Network Analysis Tools: Algorithmic Methods for Identifying Structure in Large Informatics Graphs
III:媒介:协作研究:几何网络分析工具:识别大型信息学图中结构的算法方法
- 批准号:
0963904 - 财政年份:2010
- 资助金额:
$ 45万 - 项目类别:
Continuing Grant
Collaborative Research: Spectral Graph Theory and Its Applications
合作研究:谱图理论及其应用
- 批准号:
0635357 - 财政年份:2007
- 资助金额:
$ 45万 - 项目类别:
Continuing Grant
Metric embeddings, approximation and combinatorial algorithms.
度量嵌入、近似和组合算法。
- 批准号:
0515304 - 财政年份:2005
- 资助金额:
$ 45万 - 项目类别:
Continuing Grant
Information Technology Research (ITR): Building the Tree of Life -- A National Resource for Phyloinformatics and Computational Phylogenetics
信息技术研究(ITR):构建生命之树——系统信息学和计算系统发育学的国家资源
- 批准号:
0331494 - 财政年份:2003
- 资助金额:
$ 45万 - 项目类别:
Cooperative Agreement
Network Algorithms: Scheduling and Routing
网络算法:调度和路由
- 批准号:
0105533 - 财政年份:2001
- 资助金额:
$ 45万 - 项目类别:
Continuing Grant
相似国自然基金
员工算法规避行为的内涵结构、量表开发及多层次影响机制:基于大(小)数据研究方法整合视角
- 批准号:72372021
- 批准年份:2023
- 资助金额:40 万元
- 项目类别:面上项目
基于球面约束和小波框架正则化的磁共振图像处理变分模型与快速算法
- 批准号:12301545
- 批准年份:2023
- 资助金额:30 万元
- 项目类别:青年科学基金项目
基于谱图小波变换算法的2型糖尿病肠道微生物组学网络标志物筛选研究
- 批准号:82204161
- 批准年份:2022
- 资助金额:30.00 万元
- 项目类别:青年科学基金项目
基于谱图小波变换算法的2型糖尿病肠道微生物组学网络标志物筛选研究
- 批准号:
- 批准年份:2022
- 资助金额:30 万元
- 项目类别:青年科学基金项目
用于非小细胞肺癌免疫疗效预测的复合传感模式电子鼻构建及智能算法研究
- 批准号:62176220
- 批准年份:2021
- 资助金额:57.00 万元
- 项目类别:面上项目
相似海外基金
Collaborative Research: AF: Small: Structural Graph Algorithms via General Frameworks
合作研究:AF:小型:通过通用框架的结构图算法
- 批准号:
2347322 - 财政年份:2024
- 资助金额:
$ 45万 - 项目类别:
Standard Grant
AF:RI:Small: Fairness in allocation and machine learning problems: algorithms and solution concepts
AF:RI:Small:分配公平性和机器学习问题:算法和解决方案概念
- 批准号:
2334461 - 财政年份:2024
- 资助金额:
$ 45万 - 项目类别:
Standard Grant
AF: Small: Communication-Aware Algorithms for Dynamic Allocation of Heterogeneous Resources
AF:小型:用于异构资源动态分配的通信感知算法
- 批准号:
2335187 - 财政年份:2024
- 资助金额:
$ 45万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: Structural Graph Algorithms via General Frameworks
合作研究:AF:小型:通过通用框架的结构图算法
- 批准号:
2347321 - 财政年份:2024
- 资助金额:
$ 45万 - 项目类别:
Standard Grant