AF: Small: Nearly Linear-Time Algorithms for Mixed Packing and Covering Linear Programs

AF:小:混合打包和覆盖线性程序的近线性时间算法

基本信息

  • 批准号:
    1117954
  • 负责人:
  • 金额:
    $ 10.2万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Standard Grant
  • 财政年份:
    2011
  • 资助国家:
    美国
  • 起止时间:
    2011-08-01 至 2014-07-31
  • 项目状态:
    已结题

项目摘要

On both practical and theoretical levels, linear programming is one of the most important optimization problems studied in Computer Science and Operations Research. But, on both levels, our current understanding of linear programming has substantial room for improvement. Theoretically, the worst-case time bounds that are known for current algorithms are far higher than what is observed in practice. Although the recent development of smoothed analysis gives polynomial-bounded running time on certain kinds of instances, the bounds are still very high-degree polynomials, much larger than what we see in practice. Our current theoretical models do not accurately model how linear-programming algorithms behave in practice. Practically, current algorithms often take time quadratic in the size of the input (even to find approximate, as opposed to optimal, solutions). An ideal algorithm should take linear, or nearly linear, time. State-of-the-art implementations (such as CPLEX) are generally commercially developed, taking research on them out of the public/academic domain. Effective implementation of Simplex and Interior-Point algorithms is difficult, as evidenced by the performance gap between free and commercial solvers and the cost of the best commercial solvers. To solve very large problems, even the most effective implementations sometimes require manual testing and tuning, and even then can be unpredictably slow. Existing algorithms leave room for improvement on several fronts, including ease of implementation, ease of use, numerical stability, public accessibility, running time, and good theoretical analyses. Given the widespread practical and commercial importance of linear programming, the development and publication of algorithms with provably good worst-case running times, provable numerical stability, and relatively simple, open-source implementations, have the potential for broad practical and commercial impact. The goal of the project is to make progress in this direction by designing provably fast (nearly linear time) and numerically robust approximation algorithms for very large linear-programming problems. The project focuses on algorithms for so-called mixed packing and covering linear programs --- an important special case in which all coefficients in the constraint matrix are non-negative. In practice, for problem instances having more than thousands of rows and columns, the goal of the project is algorithms that find solutions within 1% of optimal, and do so orders of magnitude more quickly than algorithms now used in practice (Simplex, Interior Point, and Ellipsoid). The algorithms should be numerically stable --- requiring no special treatment of instances with ill-conditioned constraint matrices. The algorithms will be made publically available via implementations and open-source publications.
线性规划是计算机科学与运筹学中最重要的优化问题之一,无论在实践层面还是理论层面上都是如此。但是,在这两个层面上,我们目前对线性规划的理解还有很大的改进空间。从理论上讲,已知当前算法的最坏情况时间界限远高于实践中观察到的情况。尽管光滑分析的最新发展在某些实例上给出了多项式有界的运行时间,但其范围仍然是非常高的多项式,比我们在实践中看到的要大得多。我们目前的理论模型不能准确地模拟线性规划算法在实践中的行为。实际上,当前的算法通常花费的时间是输入大小的二次(即使是找到近似的,而不是最优的,解决方案)。理想的算法应该是线性的,或者近似线性的。最先进的实现(如CPLEX)通常是商业开发的,将对它们的研究从公共/学术领域中分离出来。单纯形和内点算法的有效实现是困难的,免费和商业求解器之间的性能差距以及最佳商业求解器的成本证明了这一点。要解决非常大的问题,即使是最有效的实现有时也需要手动测试和调优,即使这样也可能慢得不可预测。现有算法在几个方面还有改进的空间,包括易于实现、易于使用、数值稳定性、公共可访问性、运行时间和良好的理论分析。考虑到线性规划广泛的实际和商业重要性,开发和发布具有可证明的良好最坏情况运行时间、可证明的数值稳定性和相对简单的开源实现的算法,具有广泛的实际和商业影响的潜力。该项目的目标是通过为非常大的线性规划问题设计可证明的快速(近线性时间)和数值鲁棒近似算法,在这个方向上取得进展。该项目专注于所谓的混合包装和覆盖线性规划的算法——约束矩阵中所有系数都是非负的重要特殊情况。在实践中,对于具有超过数千行和列的问题实例,项目的目标是在最优的1%以内找到解决方案的算法,并且比现在在实践中使用的算法(Simplex、Interior Point和Ellipsoid)快几个数量级。算法在数值上应该是稳定的——不需要对带有病态约束矩阵的实例进行特殊处理。这些算法将通过实现和开源出版物公开提供。

项目成果

期刊论文数量(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 }}

Neal Young其他文献

Telomere length and associations with somatic mutations and clinical outcomes in acute myeloid leukemia
  • DOI:
    10.1016/j.leukres.2016.07.013
  • 发表时间:
    2016-10-01
  • 期刊:
  • 影响因子:
  • 作者:
    Justin M. Watts;Bogdan Dumitriu;Patrick Hilden;Ashwin Kishtagari;Franck Rapaport;Christina Chen;Jihae Ahn;Sean M. Devlin;Eytan M. Stein;Raajit Rampal;Ross L. Levine;Neal Young;Martin S. Tallman
  • 通讯作者:
    Martin S. Tallman
Rapid determination of salicylate in serum on a centrifugal analyzer
  • DOI:
    10.1016/s0009-9120(84)80152-6
  • 发表时间:
    1984-06-01
  • 期刊:
  • 影响因子:
  • 作者:
    Tai Kwong;Norman Adams;Neal Young
  • 通讯作者:
    Neal Young
Multiple sclerosis and the workplace
多发性硬化症和工作场所
  • DOI:
  • 发表时间:
    1987
  • 期刊:
  • 影响因子:
    9.9
  • 作者:
    E. Stein;R. Schiffer;W. J. Hall;Neal Young
  • 通讯作者:
    Neal Young
Protease inhibitors stimulate hematopoiesis and decrease apoptosis and ICE expression in CD34<sup>+</sup> cells
  • DOI:
    10.1182/blood.v96.8.2735
  • 发表时间:
    2000-10-15
  • 期刊:
  • 影响因子:
  • 作者:
    Elaine M. Sloand;Jaroslaw Maciejewski;Princy Kumar;Sonnie Kim;Aniruddho Chaudhuri;Neal Young
  • 通讯作者:
    Neal Young
Measured Velocities and Ice Flow in Wilkes Land, Antarctica
南极洲威尔克斯地的测量速度和冰流
  • DOI:
  • 发表时间:
    1989
  • 期刊:
  • 影响因子:
    2.9
  • 作者:
    Neal Young;Ian D. Goodwin;N. W. J. Hazelton;R. Thwaites
  • 通讯作者:
    R. Thwaites

Neal Young的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Neal Young', 18)}}的其他基金

III: Small: Increase the Throughput of Non-Relational Databases through Theoretical Modeling and Optimization
III:小:通过理论建模和优化提高非关系数据库的吞吐量
  • 批准号:
    1619463
  • 财政年份:
    2016
  • 资助金额:
    $ 10.2万
  • 项目类别:
    Standard Grant
Approximation Algorithms for Combinatorial Optimization
组合优化的近似算法
  • 批准号:
    0729071
  • 财政年份:
    2007
  • 资助金额:
    $ 10.2万
  • 项目类别:
    Standard Grant
Career: Combinational Approximation Algorithms
职业:组合逼近算法
  • 批准号:
    9720664
  • 财政年份:
    1998
  • 资助金额:
    $ 10.2万
  • 项目类别:
    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 万元
  • 项目类别:
    重大研究计划

相似海外基金

Powering Small Craft with a Novel Ammonia Engine
用新型氨发动机为小型船只提供动力
  • 批准号:
    10099896
  • 财政年份:
    2024
  • 资助金额:
    $ 10.2万
  • 项目类别:
    Collaborative R&D
"Small performances": investigating the typographic punches of John Baskerville (1707-75) through heritage science and practice-based research
“小型表演”:通过遗产科学和基于实践的研究调查约翰·巴斯克维尔(1707-75)的印刷拳头
  • 批准号:
    AH/X011747/1
  • 财政年份:
    2024
  • 资助金额:
    $ 10.2万
  • 项目类别:
    Research Grant
Fragment to small molecule hit discovery targeting Mycobacterium tuberculosis FtsZ
针对结核分枝杆菌 FtsZ 的小分子片段发现
  • 批准号:
    MR/Z503757/1
  • 财政年份:
    2024
  • 资助金额:
    $ 10.2万
  • 项目类别:
    Research Grant
Bacteriophage control of host cell DNA transactions by small ORF proteins
噬菌体通过小 ORF 蛋白控制宿主细胞 DNA 交易
  • 批准号:
    BB/Y004426/1
  • 财政年份:
    2024
  • 资助金额:
    $ 10.2万
  • 项目类别:
    Research Grant
Windows for the Small-Sized Telescope (SST) Cameras of the Cherenkov Telescope Array (CTA)
切伦科夫望远镜阵列 (CTA) 小型望远镜 (SST) 相机的窗口
  • 批准号:
    ST/Z000017/1
  • 财政年份:
    2024
  • 资助金额:
    $ 10.2万
  • 项目类别:
    Research Grant
CSR: Small: Leveraging Physical Side-Channels for Good
CSR:小:利用物理侧通道做好事
  • 批准号:
    2312089
  • 财政年份:
    2024
  • 资助金额:
    $ 10.2万
  • 项目类别:
    Standard Grant
CSR: Small: Multi-FPGA System for Real-time Fraud Detection with Large-scale Dynamic Graphs
CSR:小型:利用大规模动态图进行实时欺诈检测的多 FPGA 系统
  • 批准号:
    2317251
  • 财政年份:
    2024
  • 资助金额:
    $ 10.2万
  • 项目类别:
    Standard Grant
AF: Small: Problems in Algorithmic Game Theory for Online Markets
AF:小:在线市场的算法博弈论问题
  • 批准号:
    2332922
  • 财政年份:
    2024
  • 资助金额:
    $ 10.2万
  • 项目类别:
    Standard Grant
Collaborative Research: FET: Small: Algorithmic Self-Assembly with Crisscross Slats
合作研究:FET:小型:十字交叉板条的算法自组装
  • 批准号:
    2329908
  • 财政年份:
    2024
  • 资助金额:
    $ 10.2万
  • 项目类别:
    Standard Grant
NeTS: Small: ML-Driven Online Traffic Analysis at Multi-Terabit Line Rates
NeTS:小型:ML 驱动的多太比特线路速率在线流量分析
  • 批准号:
    2331111
  • 财政年份:
    2024
  • 资助金额:
    $ 10.2万
  • 项目类别:
    Standard Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了