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

点击翻译按钮获取中文摘要

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.