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其他文献

The k-traveling repairman problem
k-旅行修理工问题
  • DOI:
  • 发表时间:
    2003
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Jittat Fakcharoenphol;Chris Harrelson;Satish Rao
  • 通讯作者:
    Satish Rao
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
  • 期刊:
  • 影响因子:
    3.8
  • 作者:
    Arindam Chakraborty;P. Adhikari;S. Shenoy;Satish Rao;B. Dhanashree;V. Saralaya
  • 通讯作者:
    V. Saralaya
Congestion-Approximators from the Bottom Up
自下而上的拥塞近似器
  • DOI:
  • 发表时间:
    2024
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Jason Li;Satish Rao;Di Wang
  • 通讯作者:
    Di Wang
Geometric Embeddings and Graph Partitioning
几何嵌入和图分区
  • DOI:
  • 发表时间:
    2008
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Sanjeev Arora;Satish Rao
  • 通讯作者:
    Satish Rao
Sideroblastic Anemia Associated With Isoniazid Prophylaxis in a Person Living With HIV.
铁粒幼细胞贫血与艾滋病毒感染者的异烟肼预防相关。
  • DOI:
    10.1097/mjt.0000000000000962
  • 发表时间:
    2019
  • 期刊:
  • 影响因子:
    4.2
  • 作者:
    Satish Rao;N. Murali;Vamshi Dharan Permi;A. Shetty
  • 通讯作者:
    A. Shetty

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
Explorations in Algorithms
算法探索
  • 批准号:
    0830797
  • 财政年份:
    2008
  • 资助金额:
    $ 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

相似国自然基金

昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
  • 批准号:
  • 批准年份:
    2024
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
  • 批准号:
    n/a
  • 批准年份:
    2022
  • 资助金额:
    10.0 万元
  • 项目类别:
    省市级项目
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
  • 批准号:
    32000033
  • 批准年份:
    2020
  • 资助金额:
    24.0 万元
  • 项目类别:
    青年科学基金项目
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
  • 批准号:
    31972324
  • 批准年份:
    2019
  • 资助金额:
    58.0 万元
  • 项目类别:
    面上项目
变异链球菌small RNAs连接LuxS密度感应与生物膜形成的机制研究
  • 批准号:
    81900988
  • 批准年份:
    2019
  • 资助金额:
    21.0 万元
  • 项目类别:
    青年科学基金项目
肠道细菌关键small RNAs在克罗恩病发生发展中的功能和作用机制
  • 批准号:
    31870821
  • 批准年份:
    2018
  • 资助金额:
    56.0 万元
  • 项目类别:
    面上项目
基于small RNA 测序技术解析鸽分泌鸽乳的分子机制
  • 批准号:
    31802058
  • 批准年份:
    2018
  • 资助金额:
    26.0 万元
  • 项目类别:
    青年科学基金项目
Small RNA介导的DNA甲基化调控的水稻草矮病毒致病机制
  • 批准号:
    31772128
  • 批准年份:
    2017
  • 资助金额:
    60.0 万元
  • 项目类别:
    面上项目
基于small RNA-seq的针灸治疗桥本甲状腺炎的免疫调控机制研究
  • 批准号:
    81704176
  • 批准年份:
    2017
  • 资助金额:
    20.0 万元
  • 项目类别:
    青年科学基金项目
水稻OsSGS3与OsHEN1调控small RNAs合成及其对抗病性的调节
  • 批准号:
    91640114
  • 批准年份:
    2016
  • 资助金额:
    85.0 万元
  • 项目类别:
    重大研究计划

相似海外基金

Collaborative Research: AF: Small: Structural Graph Algorithms via General Frameworks
合作研究:AF:小型:通过通用框架的结构图算法
  • 批准号:
    2347322
  • 财政年份:
    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
AF: Small: Algorithms for Graph Cuts
AF:小:图割算法
  • 批准号:
    2329230
  • 财政年份:
    2023
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
AF: Small: New Challenges and Approaches in Clustering Algorithms
AF:小:聚类算法的新挑战和方法
  • 批准号:
    2311397
  • 财政年份:
    2023
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
AF: Small: RUI: Toward High-Performance Block Krylov Subspace Algorithms for Solving Large-Scale Linear Systems
AF:小:RUI:用于求解大规模线性系统的高性能块 Krylov 子空间算法
  • 批准号:
    2327619
  • 财政年份:
    2023
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
SHF: AF: Small: Algorithms and a Code Generator for Faster Stencil Computations
SHF:AF:Small:用于更快模板计算的算法和代码生成器
  • 批准号:
    2318633
  • 财政年份:
    2023
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
AF: SMALL: Relational Algorithms
AF:小:关系算法
  • 批准号:
    2209654
  • 财政年份:
    2022
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
NSF-BSF: AF: Small: Algorithms for Graph-Based Codes
NSF-BSF:AF:小型:基于图形的代码算法
  • 批准号:
    2133154
  • 财政年份:
    2022
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
AF: Small: Towards New Relaxations for Online Algorithms
AF:小:在线算法的新放松
  • 批准号:
    2224718
  • 财政年份:
    2022
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了