Author name cluster

Kook Jin Ahn

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

2 author rows

ICML Conference 2015 Conference Paper

Correlation Clustering in Data Streams

Kook Jin Ahn
Graham Cormode
Sudipto Guha
Andrew McGregor 0001
Anthony Wirth

In this paper, we address the problem of \emphcorrelation clustering in the dynamic data stream model. The stream consists of updates to the edge weights of a graph on n nodes and the goal is to find a node-partition such that the end-points of negative-weight edges are typically in different clusters whereas the end-points of positive-weight edges are typically in the same cluster. We present polynomial-time, O(n⋅\textpolylog n)-space approximation algorithms for natural problems that arise. We first develop data structures based on linear sketches that allow the “quality” of a given node-partition to be measured. We then combine these data structures with convex programming and sampling techniques to solve the relevant approximation problem. However the standard LP and SDP formulations are not obviously solvable in O(n⋅\textpolylog n)-space. Our work presents space-efficient algorithms for the convex programming required, as well as approaches to reduce the adaptivity of the sampling. Note that the improved space and running-time bounds achieved from streaming algorithms are also useful for offline settings such as MapReduce models.

Details

SODA Conference 2014 Conference Paper

Near Linear Time Approximation Schemes for Uncapacitated and Capacitated b-Matching Problems in Nonbipartite Graphs

Kook Jin Ahn
Sudipto Guha

We present the first fully polynomial approximation schemes for the maximum weighted (uncapacitated or capacitated) b –Matching problem for nonbipartite graphs that run in time (near) linear in the number of edges, that is, given any δ > 0 the algorithm produces a (1 – δ ) approximation in O ( m poly( δ −1, log n )) time. We provide fractional solutions for the standard linear programming formulations for these problems and subsequently also provide fully polynomial (near) linear time approximation schemes for rounding the fractional solutions. Through these problems as a vehicle, we also present several ideas in the context of solving linear programs approximately using fast primal-dual algorithms. First, we show that approximation algorithms can be used to reduce the width of the formulation, and as a consequence we induce faster convergence. Second, even though the dual of these problems have exponentially many variables and an efficient exact computation of dual weights is infeasible, we can efficiently compute and use a sparse approximation of the dual weights using a combination of (i) adding perturbation to the constraints of the polytope and (ii) amplification followed by thresholding of the dual weights. These algorithms also have the advantage that they use O ( n poly( δ −1, log n )) storage space and only make O ( δ −4 log (1/ δ )log n ) (or better) passes over a read only list of edges. These algorithms therefore can be run in the semi-streaming model and serve as exemplars where algorithms and ideas developed for the streaming model gives us algorithms for combinatorial optimization problems that were not known in absence of the streaming constraints.

Details

I&C Journal 2013 Journal Article

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. In this model edges are presented sequentially, possibly in an adversarial order, and we are only allowed to use a small space. The allowed space is near linear in the number of vertices (and sublinear in the number of edges) of the input graph. The semi-streaming model is relevant in the context of processing of very large graphs. In recent years, there have been several new and exciting results in the semi-streaming model. However broad techniques such as linear programming have not been adapted to this model. In this paper we present several techniques to adapt and optimize linear-programming based approaches in the semi-streaming model. We use the maximum matching problem as a foil to demonstrate the effectiveness of adapting such tools in this model. As a consequence we improve almost all previous results on the semi-streaming maximum matching problem. We also prove new results on interesting variants.

Details DOI

SODA Conference 2012 Conference Paper

Analyzing graph structure via linear measurements

Kook Jin Ahn
Sudipto Guha
Andrew McGregor 0001

We initiate the study of graph sketching, i. e. , algorithms that use a limited number of linear measurements of a graph to determine the properties of the graph. While a graph on n nodes is essentially O ( n 2 )-dimensional, we show the existence of a distribution over random projections into d -dimensional “sketch” space ( d ≪ n 2 ) such that the relevant properties of the original graph can be inferred from the sketch with high probability. Specifically, we show that: 1. d = O ( n · polylog n ) suffices to evaluate properties including connectivity, k -connectivity, bipartiteness, and to return any constant approximation of the weight of the minimum spanning tree. 2. d = O ( n 1+γ ) suffices to compute graph sparsifiers, the exact MST, and approximate the maximum weighted matchings if we permit O (1/γ)-round adaptive sketches, i. e. , a sequence of projections where each projection may be chosen dependent on the outcome of earlier sketches.

Details