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)图结构和算法，(c)随机化和(d)数据结构的丰富和及时的相互作用。它们被分为以下垂直方向。第一组，关于加速正线性规划，着重于减少对组合优化中有用的各种线性规划的相对误差参数的运行时间依赖。第二组问题，关于旅行推销员问题（TSP）的快速逼近，寻求发展TSP变化的线性时间逼近以及相关的独立兴趣问题。第三组也是最后一组问题开发了连接的快速近似算法，包括无向图和有向图的问题。这些问题之间有丰富的理论联系，本项目利用和进一步发展。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

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

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

Faster Algorithms for Rooted Connectivity in Directed Graphs

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

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

Convergence to Lexicographically Optimal Base in a (Contra)Polymatroid and Applications to Densest Subgraph and Tree Packing

• DOI: 10.48550/arxiv.2305.02987
• 发表时间: 2023-05
• 期刊: ArXiv
• 作者: Elfarouk Harb;Kent Quanrud;C. Chekuri