A general approach for incremental approximation and hierarchical clustering
Guolong Lin, Chandrashekhar Nagarajan, Rajmohan Rajaraman, David P. Williamson · Symposium on Discrete Algorithms · 2006
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 any k and k', k