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

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

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.