Brief Announcement: Applications of Uniform Sampling: Densest Subgraph and Beyond
Title | Brief Announcement: Applications of Uniform Sampling: Densest Subgraph and Beyond |
Publication Type | Conference Paper |
Year of Publication | 2016 |
Authors | Esfandiari, Hossein, Hajiaghayi, MohammadTaghi, Woodruff, David P. |
Conference Name | Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures |
Publisher | ACM |
Conference Location | New York, NY, USA |
ISBN Number | 978-1-4503-4210-0 |
Keywords | Collaboration, data deletion, densest subgraph, Human Behavior, pubcrawl, Scalability, streaming algorithm, uniform sampling |
Abstract | In this paper we provide a framework to analyze the effect of uniform sampling on graph optimization problems. Interestingly, we apply this framework to a general class of graph optimization problems that we call heavy subgraph problems, and show that uniform sampling preserves a 1-e approximate solution to these problems. This class contains many interesting problems such as densest subgraph, directed densest subgraph, densest bipartite subgraph, d-max cut, and d-sum-max clustering. As an immediate impact of this result, one can use uniform sampling to solve these problems in streaming, turnstile or Map-Reduce settings. Indeed, our results by characterizing heavy subgraph problems address Open Problem 13 at the IITK Workshop on Algorithms for Data Streams in 2006 regarding the effects of subsampling, in the context of graph streams. Recently Bhattacharya et al. in STOC 2015 provide the first one pass algorithm for the densest subgraph problem in the streaming model with additions and deletions to its edges, i.e., for dynamic graph streams. They present a (0.5-e)-approximation algorithm using \textasciitildeO(n) space, where factors of e and log(n) are suppressed in the \textasciitildeO notation. In this paper we improve the (0.5-e)-approximation algorithm of Bhattacharya et al. by providing a (1-e)-approximation algorithm using \textasciitildeO(n) space. |
URL | http://doi.acm.org/10.1145/2935764.2935813 |
DOI | 10.1145/2935764.2935813 |
Citation Key | esfandiari_brief_2016 |