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

AF：EAGER：图优化问题的小空间算法和表示

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

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.

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