Combinatorial Optimization Reading Group- Sharat IbrahimpurExport this event to calendar

Friday, November 30, 2018 — 1:00 PM EST

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.

Location 
MC - Mathematics & Computer Building
5479
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
  1. 2019 (141)
    1. October (12)
    2. September (15)
    3. August (9)
    4. July (17)
    5. June (18)
    6. May (16)
    7. April (9)
    8. March (24)
    9. February (13)
    10. January (8)
  2. 2018 (138)
    1. December (2)
    2. November (18)
    3. October (14)
    4. September (9)
    5. August (2)
    6. July (10)
    7. June (13)
    8. May (17)
    9. April (9)
    10. March (19)
    11. February (14)
    12. January (11)
  3. 2017 (103)
  4. 2016 (137)
  5. 2015 (136)
  6. 2014 (88)
  7. 2013 (48)
  8. 2012 (39)
  9. 2011 (36)
  10. 2010 (40)
  11. 2009 (40)
  12. 2008 (39)
  13. 2007 (15)