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

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

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.