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

University Of Pennsylvania, Philadelphia PA

Investigators

Abstract

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.