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

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

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.