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的法定使命，并被认为是值得通过使用基金会的知识价值和更广泛的影响审查标准进行评估的支持。

项目成果

Sublinear Algorithms for Hierarchical Clustering

• DOI: 10.48550/arxiv.2206.07633
• 发表时间: 2022-06
• 期刊: ArXiv
• 作者: Arpit Agarwal;S. Khanna;Huan Li;Prathamesh Patil

New Trade-Offs for Fully Dynamic Matching via Hierarchical EDCS

通过分层 EDCS 实现完全动态匹配的新权衡

• DOI: 10.1137/1.9781611977073.140
• 发表时间: 2022
• 期刊: Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA
• 作者: Behnezhad, Soheil;Khanna, Sanjeev.
• 通讯作者: Khanna, Sanjeev.

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

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

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

Sublinear Time Hypergraph Sparsification via Cut and Edge Sampling Queries

• DOI: 10.4230/lipics.icalp.2021.53
• 发表时间: 2021-06
• 作者: Yu Chen;S. Khanna;Ansh Nagda

Approximate optimization of convex functions with outlier noise

具有离群噪声的凸函数的近似优化

• 发表时间: 2021
• 期刊: Advances in neural information processing systems
• 作者: De, Anindya;Khanna, Sanjeev;Li, Huan;Nikpey, Hesam
• 通讯作者: Nikpey, Hesam