Approximation algorithms for clustering
We work on designing and analyzing approximation algorithms for various theoretical models of clustering. Clustering is the problem of partitioning data items according to similarity. This can be seen as an optimization problem where the objective function, for example, the maximum cluster radius, measures the quality of the clustering, and most versions of the problem are NP-hard. We aim to relate and criticize existing models, analyze common algorithms in detail, and design algorithms with better approximation ratio.
Project status: Active
Research Areas
| Combinatorial Optimization |
People
| Aparna Das |
| Claire Mathieu |
Publications
Chrobak, M., Kenyon, C., Noga, J., and Young, N. E. Online medians via online bribery. In LATIN 2006: Theoretical Informatics (Valdivia, Chile, Mar 2006), J. R. Correa, A. Hevia, and M. Kiwi, Eds., pp. 311-322.
Chroback, M., Kenyon, C., and Young, N. The Reverse Greedy Algorithm for the Metric K-Median Problem. Information Processing Letters, 2 (Jan 2006), 68-72. [ pdf ]
Das, A., and Kenyon, C. On hierarchical diameter-clustering, and the supplier problems. In Fourth Workshop on Approximation and Online Algorithms (Zurich, Sep 2006), Springer Verlag, Lecture Notes in Computer Science. [ pdf ]
de la Vega, W. F., Karpinski, M., and Kenyon, C. Approximation Schemes for Metric Bisection and Partitioning. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2004), pp. 506-515. [ pdf ]
de la Vega, W. F., Karpinski, M., Kenyon, C., and Rabani, Y. Approximation Schemes for Clustering Problems. In Thirty-Fifth Annual ACM Symposium on Theory of Computing (STOC) (2003), pp. 50-58. [ pdf ]
| Page Owner: Webmaster | Last Modified: Mon Oct 23 14:57:09 2006 |