Visible to the public Brief Announcement: Applications of Uniform Sampling: Densest Subgraph and Beyond

TitleBrief Announcement: Applications of Uniform Sampling: Densest Subgraph and Beyond
Publication TypeConference Paper
Year of Publication2016
AuthorsEsfandiari, Hossein, Hajiaghayi, MohammadTaghi, Woodruff, David P.
Conference NameProceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures
PublisherACM
Conference LocationNew York, NY, USA
ISBN Number978-1-4503-4210-0
KeywordsCollaboration, 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.

URLhttp://doi.acm.org/10.1145/2935764.2935813
DOI10.1145/2935764.2935813
Citation Keyesfandiari_brief_2016