AF: Small: Sublinear Algorithms for Flows, Matchings, and Routing Problems

AF：小：流、匹配和路由问题的次线性算法

• 批准号: 2008305
• 负责人: Sanjeev Khanna
• 金额: $ 45万
• 依托单位: University of Pennsylvania
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-07-01 至 2024-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2008305&HistoricalAwards=false
• 关键词: AF; Small; Sublinear; Algorithms; Flows

Very large-scale graphs routinely arise in applications where the data describes pairwise relationships among a set of objects. The widespread prevalence of such graphs has led to the emergence of new computational models that allow for efficient processing of information contained in these large networks. Traditional gold standards of computational efficiency, namely, linear storage requirements, linear running time, and linear communication overhead as a function of problem size have given way to sublinear algorithms that use resources that are much smaller than the input size. The goal of this project is to design sublinear algorithms for several fundamental graph problems as well as explore limits of such algorithms. The research activities in this project will go hand-in-hand with educational and student-training initiatives, as well as outreach efforts to engage high-school students and under-represented groups in computer science and related disciplines. The project will also support and train PhD students whose dissertation work will be closely aligned with the proposed research. The project is broadly divided into three parts. The first part considers sublinear space and sublinear time algorithms for the matching problem. The sublinear space algorithms are in the setting of the streaming model of computation where the edges of an underlying graph are revealed as a sequence of edge insertion and deletion updates, and the goal is to compute a near-optimal solution using a small amount of space. The sublinear time algorithms are in the setting of the standard query access model where the graph can be accessed via adjacency-list queries. The second part considers communication-efficient protocols for flows and matchings in the setting where the edges of a graph are arbitrarily distributed among two players, and the goal is to compute an optimal or near-optimal solution with a small amount of communication. The third part considers sublinear time and space algorithms for the well-known traveling salesman problem where the goal is to estimate the cost of the cheapest traveling salesman tour. The problems considered in these three parts are intimately connected to one another and new results for any one of them are likely to have implications for the other.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.

非常大规模的图通常出现在数据描述一组对象之间的成对关系的应用程序中。此类图的广泛流行导致了新的计算模型的出现，这些模型可以有效地处理这些大型网络中包含的信息。计算效率的传统黄金标准，即线性存储要求、线性运行时间和作为问题大小函数的线性通信开销，已经让位于使用比输入大小小得多的资源的次线性算法。该项目的目标是为几个基本图问题设计次线性算法，并探索此类算法的局限性。该项目的研究活动将与教育和学生培训计划以及让高中生和弱势群体参与计算机科学和相关学科的外展工作齐头并进。该项目还将支持和培训博士生，他们的论文工作将与拟议的研究密切相关。该项目大致分为三个部分。第一部分考虑匹配问题的次线性空间和次线性时间算法。次线性空间算法是在计算流模型的设置中，其中底层图的边缘显示为边缘插入和删除更新的序列，目标是使用少量空间计算接近最优的解决方案。次线性时间算法采用标准查询访问模型的设置，其中可以通过邻接表查询来访问图。第二部分考虑在图的边缘任意分布在两个参与者之间的设置中的流和匹配的通信高效协议，目标是通过少量通信计算最优或接近最优的解决方案。第三部分考虑了著名的旅行商问题的次线性时间和空间算法，其目标是估计最便宜的旅行商旅行的成本。这三个部分所考虑的问题彼此密切相关，其中任何一个的新结果都可能对另一个产生影响。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值进行评估，被认为值得支持以及更广泛的影响审查标准。

项目成果

A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization

并行子模函数最小化轮数的多项式下界

• DOI: 10.1109/focs52979.2021.00013
• 发表时间: 2022-02
• 期刊: (FOCS
• 作者: Chakrabarty, Deeparnab;Chen, Yu;Khanna, Sanjeev
• 通讯作者: Khanna, Sanjeev

A Sharp Memory-Regret Trade-off for Multi-Pass Streaming Bandits

多通道流强盗的急剧记忆遗憾权衡

• 发表时间: 2022-07
• 期刊: Conference on Learning Theory (COLT
• 作者: Agarwal, Arpit;Khanna, Sanjeev;Patil, Prathamesh
• 通讯作者: Patil, Prathamesh

Optimal Bounds for Dominating Set in Graph Streams

图流中支配集的最优界限

• DOI: 10.4230/lipics.itcs.2022.93
• 发表时间: 2022-01
• 期刊: Leibniz international proceedings in informatics
• 作者: Khanna, Sanjeev;Konrad, Christian
• 通讯作者: Konrad, Christian

Hardness of Approximation for Orienteering with Multiple Time Windows

多时间窗定向运动的近似硬度

• 发表时间: 2021-01
• 期刊: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms
• 作者: Garg, Naveen;Khanna, Sanjeev;Kumar, Amit
• 通讯作者: Kumar, Amit

Nearly Tight Bounds for Discrete Search under Outlier Noise

离群噪声下离散搜索的近乎严格的界限

• DOI: 10.1137/1.9781611977066.11
• 发表时间: 2022-01
• 期刊: Symposium on Simplicity in Algorithms
• 作者: De, Anindya;Khanna, Sanjeev;Li, Huan;Nikpey, Hesam
• 通讯作者: Nikpey, Hesam