4 citations · 9 across the 4 of their papers we have counts for
5 papers · 1 filter
Maximum Coverage in the Data Stream Model: Parameterized and Generalized
Andrew McGregor, David Tench, Hoa T. Vu
We present algorithms for the Max-Cover and Max-Unique-Cover problems in the data stream model. The input to both problems are subsets of a universe of size and a value $k\…
Distributed Data Summarization in Well-Connected Networks
Hsin-Hao Su, Hoa T. Vu
We study distributed algorithms for some fundamental problems in data summarization. Given a communication graph of nodes each of which may hold a value initially, we focus…
Towards the Locality of Vizing's Theorem
Hsin-Hao Su, Hoa T. Vu
Vizing showed that it suffices to color the edges of a simple graph using colors, where is the maximum degree of the graph. However, up to this date, no efficient distri…
Densest Subgraph in Dynamic Graph Streams
Andrew McGregor, David Tench, Sofya Vorotnikova +1
In this paper, we consider the problem of approximating the densest subgraph in the dynamic graph stream model. In this model of computation, the input graph is defined by an arbit…
Run Generation Revisited: What Goes Up May or May Not Come Down
Michael A. Bender, Samuel McCauley, Andrew McGregor +2
In this paper, we revisit the classic problem of run generation. Run generation is the first phase of external-memory sorting, where the objective is to scan through the data, reor…