18 citations · 101 across the 20 of their papers we have counts for
15 papers · 1 filter
Correlation Clustering in Data Streams
Kook Jin Ahn, Graham Cormode, Sudipto Guha +2
Clustering is a fundamental tool for analyzing large data sets. A rich body of work has been devoted to designing data-stream algorithms for the relevant optimization problems such…
Distributed Partial Clustering
Sudipto Guha, Yi Li, Qin Zhang
Recent years have witnessed an increasing popularity of algorithm design for distributed data, largely due to the fact that massive datasets are often collected and stored in diffe…
Approximation Algorithms for Bayesian Multi-Armed Bandit Problems
Sudipto Guha, Kamesh Munagala
In this paper, we consider several finite-horizon Bayesian multi-armed bandit problems with side constraints which are computationally intractable (NP-Hard) and for which no optima…
Access to Data and Number of Iterations: Dual Primal Algorithms for Maximum Matching under Resource Constraints
Kook Jin Ahn, Sudipto Guha
In this paper we consider graph algorithms in models of computation where the space usage (random accessible storage, in addition to the read only input) is sublinear in the number…
Near Linear Time Approximation Schemes for Uncapacitated and Capacitated b--Matching Problems in Nonbipartite Graphs
Kook Jin Ahn, Sudipto Guha
We present the first near optimal approximation schemes for the maximum weighted (uncapacitated or capacitated) --matching problems for non-bipartite graphs that run in time (ne…
Laminar Families and Metric Embeddings: Non-bipartite Maximum Matching Problem in the Semi-Streaming Model
Kook Jin Ahn, Sudipto Guha
In this paper, we study the non-bipartite maximum matching problem in the semi-streaming model. The maximum matching problem in the semi-streaming model has received a significant…