Combinatorial Optimization Reading Group- Sharat Ibrahimpur

Friday, November 30, 2018 1:00 pm - 1:00 pm EST (GMT -05:00)

Title: Clustering under Ordered Norms

Speaker: Sharat Ibrahimpur
Affiliation: University of Waterloo
Room: MC 5479

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.