Combinatorial Optimization Reading Group- Sharat Ibrahimpur

Title: Clustering under Ordered Norms

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.