18 citations · 37 across the 6 of their papers we have counts for
6 papers
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…
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…
Linear Programming in the Semi-streaming Model with Application to the Maximum Matching Problem
Kook Jin Ahn, Sudipto Guha
In this paper, we study linear programming based approaches to the maximum matching problem in the semi-streaming model. The semi-streaming model has gained attention as a model fo…
Graph Sparsification in the Semi-streaming Model
Kook Jin Ahn, Sudipto Guha
Analyzing massive data sets has been one of the key motivations for studying streaming algorithms. In recent years, there has been significant progress in analysing distributions i…