AF: Small: Sublinear Algorithms for Graph Optimization Problems

AF：小：图优化问题的次线性算法

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

Very-large scale graphs routinely arise in applications where the data describes pairwise relationships among a set of objects. Some standard examples include the Web graph, social networks, and biological networks. The prevalence of such large data sets has led to a rapidly growing interest in the design of sublinear algorithms, that is, algorithms whose computational resource requirements are substantially smaller than the input size. As vast amounts of networked data is being collected and processed in diverse application domains, sublinear algorithms that accurately compute and describe relevant properties of the data will increasingly play an important role in computing on such data. The goal of this project is to develop sublinear algorithms for several fundamental graph optimization problems. The specific graph problems studied in this project are of both theoretical and practical interest, and are among the most well-studied problems in combinatorial optimization. Additionally, a study of these problems through the lens of sublinear algorithms is likely to yield new insights into computational aspects of these fundamental problems. The research proposed here will go hand-in-hand with educational and student-training initiatives, including mentoring and training of undergraduate and graduate students, and teaching in programs that introduce high-school students to exciting ideas in theoretical computer science.The research focus of this project is broadly divided into three parts. In the first part, the PIs consider streaming algorithms for graph problems where an input graph is revealed as a sequence of edge insertions and deletions. Some representative problems studied in this part include matching and cut problems in graphs. While both cuts and matchings have received considerable attention in the streaming literature, several important questions concerning their computability in the streaming model remain unresolved. In the second part, they consider communication-efficient protocols in a distributed setting when the input graph is partitioned across multiple sites. This model offers a natural abstraction for distributed computation and is closely related to the streaming model. A representative problem here is to understand the communication complexity of the maximum matching problem. The third part of this project investigates a new model for sketching graphs that consist of a (large) static part and a (small) dynamic part. The goal here is to understand if there exist compact sketches for several fundamental graph problems whose size is proportional to the size of the dynamic part of the input graph such that any updates to the dynamic part can be applied directly to the sketch.

超大规模图通常出现在数据描述一组对象之间的成对关系的应用程序中。一些标准示例包括网络图、社交网络和生物网络。如此大的数据集的盛行引起了人们对次线性算法设计的兴趣迅速增长，即计算资源需求远小于输入大小的算法。随着大量网络数据在不同的应用领域被收集和处理，准确计算和描述数据相关属性的次线性算法将在此类数据的计算中日益发挥重要作用。该项目的目标是为几个基本的图优化问题开发次线性算法。该项目研究的具体图问题具有理论和实践意义，是组合优化中研究最深入的问题之一。此外，通过次线性算法对这些问题的研究可能会对这些基本问题的计算方面产生新的见解。这里提出的研究将与教育和学生培训计划齐头并进，包括本科生和研究生的指导和培训，以及向高中生介绍理论计算机科学中令人兴奋的想法的项目教学。该项目大致分为三个部分。在第一部分中，PI 考虑图问题的流算法，其中输入图被显示为边缘插入和删除的序列。这部分研究的一些代表性问题包括图的匹配和切割问题。虽然剪切和匹配在流媒体文献中受到了相当多的关注，但有关它们在流媒体模型中的可计算性的几个重要问题仍未解决。在第二部分中，当输入图跨多个站点分区时，他们考虑分布式设置中的通信高效协议。该模型为分布式计算提供了自然的抽象，并且与流模型密切相关。这里的一个代表性问题是理解最大匹配问题的通信复杂度。该项目的第三部分研究了一种用于绘制图形的新模型，该模型由（大）静态部分和（小）动态部分组成。这里的目标是了解是否存在几个基本图形问题的紧凑草图，其大小与输入图的动态部分的大小成正比，以便对动态部分的任何更新都可以直接应用于草图。

项目成果

Near-linear Size Hypergraph Cut Sparsifiers

近线性尺寸超图切割稀疏器

• DOI: 10.1109/focs46700.2020.00015
• 发表时间: 2020-09-10
• 期刊: 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)
• 作者: Yu Chen;S. Khanna;Ansh Nagda
• 通讯作者: Ansh Nagda

Sublinear Time Hypergraph Sparsification via Cut and Edge Sampling Queries

通过剪切和边缘采样查询进行亚线性时间超图稀疏化

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