A General Approach for Incremental Approximation and Hierarchical Clustering
Authors:
- Guolong LinGLGuolong Lin
- Chandrashekhar NagarajanCNChandrashekhar Nagarajan
- Rajmohan RajaramanRRRajmohan Rajaraman
- David P. WilliamsonDWDavid P. Williamson
- 1 January 2010
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 39 (8) , 3633-3669
Abstract
We present a general framework and algorithmic approach for incremental approximation algorithms. The framework handles cardinality constrained minimization problems, such as the k-median and k-MST problems. Given some notion of ordering on solutions of different cardinalities k, we give solutions for all values of k such that the solutions respect the ordering and such that for any k, our solution is close in value to the value of an optimal solution of cardinality k. For instance, for the k-median problem, the notion of ordering is set inclusion, and our incremental algorithm produces solutions such that for any k and $k'$, $k<k'$, our solution of size k is a subset of our solution of size $k'$. We show that our framework applies to this incremental version of the k-median problem (introduced by Mettu and Plaxton [R. R. Mettu and C. G. Plaxton, SIAM J. Comput., 32 (2003), pp. 816–832]) and incremental versions of the k-MST problem, k-vertex cover problem, k-set cover problem, as well as the uncapacitated facility location problem (which is not cardinality-constrained). For these problems we get either new incremental algorithms or improvements over what was previously known. We also show that the framework applies to hierarchical clustering problems. In particular, we give an improved algorithm for a hierarchical version of the k-median problem introduced by Plaxton [C. G. Plaxton, J. Comput. System Sci., 72 (2006), pp. 425–443].
Keywords
This publication has 33 references indexed in Scilit:
- Approximating the Stochastic Knapsack Problem: The Benefit of AdaptivityMathematics of Operations Research, 2008
- A Faster, Better Approximation Algorithm for the Minimum Latency ProblemSIAM Journal on Computing, 2008
- Incremental Medians via Online BiddingAlgorithmica, 2007
- The reverse greedy algorithm for the metric k-median problemInformation Processing Letters, 2006
- Performance guarantees for hierarchical clusteringJournal of Computer and System Sciences, 2005
- Approximation algorithms for a hierarchically structured bin packing problemInformation Processing Letters, 2004
- Incremental Clustering and Dynamic Information RetrievalSIAM Journal on Computing, 2004
- Local Search Heuristics for k-Median and Facility Location ProblemsSIAM Journal on Computing, 2004
- Computing small partial coveringsInformation Processing Letters, 2003
- A threshold of ln n for approximating set coverJournal of the ACM, 1998