AF : Small : Fast algorithms for LPs, TSP, and Connectivity

AF：小型：LP、TSP 和连接的快速算法

• 批准号: 2129816
• 负责人: Kent Quanrud
• 金额: $ 49.93万
• 依托单位: Purdue University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-03-01 至 2025-02-28
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2129816&HistoricalAwards=false
• 关键词: AF; Small; Fast; algorithms; LPs

The field of theoretical algorithms has long emphasized the difference between polynomial and exponential running times, which has formed a sound theoretical basis for computation as a science and has also been robust to many technological advancements. Recent computing trends, featuring copious amounts of data as well as the end of Moore’s law, puts greater emphasis on extremely scalable algorithms such as those with nearly linear running times. This project addresses these modern challenges by developing faster algorithms for a selection of fundamental problems in combinatorial optimization, building towards a broad algorithmic foundation of scalable algorithms. This project augments theoretical algorithms research with efforts to develop implementations and expand applications, in part through the Computational Science and Engineering group at Purdue among other avenues. This project will support two or more PhD students and the investigator will organize activities to promote research in fast algorithms, with particular effort to recruit and train students from underrepresented minorities. The investigator will integrate modern and advanced algorithmic techniques informed by the research initiatives of this project into the curriculum at Purdue both at the undergraduate and graduate level.This project encompasses a family of interrelated problems that investigate the rich and timely interplay of (a) linear programs and continuous optimization, (b) graph structure and algorithms, (c) randomization, and (d) data structures. They are grouped into the following verticals. The first group, on accelerating positive linear programs, focuses on reducing the running-time dependence on the relative-error parameter for a variety of linear programs useful in combinatorial optimization. The second group of problems, on fast approximations for the traveling salesman problem (TSP), seeks to develop linear-time approximations for variations of TSP as well as related problems of independent interest. The third and final group of problems develops fast approximation algorithms for connectivity, including problems for both undirected and directed graphs. There are rich theoretical connections across these problems that this project leverages and further develops.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.

理论算法的领域长期以来一直强调多项式运行时间和指数运行时间之间的差异，这已经形成了计算作为一门科学的合理理论基础，并且对许多技术进步也很强大。最近的计算趋势以大量数据以及摩尔定律的终结为特征，更加重视极其可扩展的算法，例如具有几乎线性运行时间的算法。该项目通过开发更快的算法来解决这些现代挑战，以选择组合优化的基本问题，从而建立了可扩展算法的广泛算法基础。该项目通过努力开发实施和扩展应用程序，部分通过普渡大学的计算科学和工程组以及其他途径来扩展理论算法研究。该项目将支持两名或多个博士学位学生，调查员将组织活动，以促进快速算法的研究，并特别努力招募和培训来自代表性不足的少数群体的学生。研究者将整合该项目的研究计划所告知的现代和先进的算法技术，包括本科和研究生级的普渡大学的课程。该项目涵盖了一个相互关联的问题，这些问题涵盖了一个相互关联的问题，这些问题涵盖了（a）线性程序和持续优化的图形结构和（b）（b）（b）（b）（b）（b）（b）（b）（b）（b）（b）（b）（b）（b）（b）（b）（b）（b）（b）（b）（b）（b）（b）（b）（b）（b）（b）（b）（b）（b）（b）（b）（c）（c）（c）（c）。它们分为以下垂直行业。第一组在加速度正线性程序上，重点是减少对各种线性程序的相对误差参数的运行时依赖性，可用于组合优化。第二组问题是关于旅行推销员问题（TSP）的快速近似，试图开发TSP变化以及相关的独立兴趣问题的线性时间近似。第三组也是最后一组问题为连接性开发了快速的近似算法，包括无向图和有向图的问题。在这些项目中，该项目利用并进一步发展存在丰富的理论联系。该奖项反映了NSF的法定任务，并通过使用基金会的知识分子优点和更广泛的影响审查标准来评估被认为是宝贵的支持。

项目成果

Faster and Scalable Algorithms for Densest Subgraph and Decomposition

• 发表时间: 2022
• 作者: Elfarouk Harb;Kent Quanrud;C. Chekuri

Faster exact and approximation algorithms for packing and covering matroids via push-relabel

通过推送重新标签来打包和覆盖拟阵的更快的精确和近似算法

• 发表时间: 2024
• 作者: Quanrud, Kent

Faster Algorithms for Rooted Connectivity in Directed Graphs

有向图中有根连接的更快算法

• 发表时间: 2021
• 期刊: and Programming (ICALP 2021
• 作者: Chekuri, Chandra;Quanrud, Kent
• 通讯作者: Quanrud, Kent

Minimum Cuts in Directed Graphs via Partial Sparsification

通过部分稀疏化有向图的最小割

• 发表时间: 2021
• 期刊: Annual Symposium on Foundations of Computer Science
• 作者: Cen, Ruoxu;Li, Jason;Nanongkai, Danupon;Panigrahi, Debmalya;Saranurak, Thatchaphol;Quanrud, Kent
• 通讯作者: Quanrud, Kent

Independent Sets in Elimination Graphs with a Submodular Objective

• DOI: 10.48550/arxiv.2307.02022
• 发表时间: 2023-07
• 期刊: ArXiv
• 作者: C. Chekuri;Kent Quanrud