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
Das, A., and Kenyon, C. On hierarchical diameter-clustering, and the supplier problems. In Fourth Workshop on Approximation and Online Algorithms (Zurich, Sept. 2006), Springer Verlag, Lecture Notes in Computer Science. [ pdf ]
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 ]
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 |