AF: EAGER: Small Space Algorithms and Representations for Graph Optimization Problems

随着非常大的数据集变得越来越普遍，人们对设计次线性算法(其资源需求大大小于输入大小的算法)和开发数据的压缩表示法的兴趣迅速增长。这个项目的重点是为一些基本的图优化问题设计次线性空间算法和压缩表示，这些问题是计算机科学和相关学科中许多应用所固有的。拟议的研究大致分为两个部分。该项目的第一部分考虑了对流模型中的图优化问题的次线性空间算法，其中输入图被表示为一系列边更新。特别是，本项目的这一部分针对最大割和最大匹配的近似问题研究了流算法。在提案的第二部分，引入了一类新的草图问题，其目标是创建一种压缩表示法，允许对预先指定的输入数据子集进行任意更新。提出的研究考虑了可更新的紧凑型草图的设计，以解决关于图中的切割、流动和匹配的问题。随着海量的网络数据在不同的应用领域被收集和处理，用于计算和描述图的相关性质的小空间算法和压缩表示将发挥越来越重要的作用。这里提出的研究将与教育和学生培训计划齐头并进。PI将在高级课程中整合拟议研究的主题，为研究生和本科生提供有针对性的研究机会。该项目还将支持和培训博士生，他们的论文工作将与拟议的研究保持一致。该项目还将支持皮？S正在进行的向高中生介绍理论计算机科学的令人兴奋的想法的工作。

As very large data sets become more prevalent, there is a rapidly growing interest in design of sublinear algorithms (algorithms whose resource requirements are substantially smaller than the size of the input) and in developing compressed representations of data. The focus of this project is to design sublinear space algorithms and compressed representations for several fundamental graph optimization problems that are intrinsic to many applications in computer science and related disciplines. The proposed research is broadly divided into two parts. The first part of the project considers sublinear space algorithms for graph optimization problems in the streaming model where an input graph is presented as a sequence of edge updates. In particular, this part of the project studies streaming algorithms for the problems of approximating the maximum cut and the maximum matching. In the second part of the proposal, a new class of sketching problems is introduced whereby the goal is to create a compressed representation that allows for arbitrary updates to a pre-specified subset of the input data. The proposed research considers design of updatable compact sketches for problems concerning cuts, flows, and matchings in graphs. Small space algorithms and compressed representations that compute and describe relevant properties of graphs will play an increasingly important role as vast amounts of networked data is being collected and processed in diverse application domains. The research proposed here will go hand-in-hand with educational and student-training initiatives. The PI will integrate topics from proposed research in advanced courses that will provide focused research opportunities for graduate and undergraduate students. The project will also support and train PhD students whose dissertation work will be aligned with the proposed research. The project will also support PI?s on-going work on introducing high-school students to exciting ideas in theoretical computer science.