Title: Clustering under Ordered Norms
|Affiliation:||University of Waterloo|
Abstract: In this talk we will see approximation algorithms for a broad class of objective functions called as ordered norms. In particular, we will see a 9+eps-approximation for the top-r / r-centrum problem where the objective is to open k facilities so that the sum of r largest assignment costs is minimized. When r=1 we get the k-center problem and when r equals the number of clients we get the k-median problem. If time permits, I will show an improved 5+eps-approximation for top-r norm and more general ordered norms.
This work is based on recent work by Chakrabarty and Swamy.
200 University Avenue West
Waterloo, ON N2L 3G1