Combinatorial Optimization Reading Group- Adam BrownExport this event to calendar

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

Title: Stability Yields a PTAS for k-Median and k-Means Clustering

Speaker: Adam Brown
Affiliation: University of Waterloo
Room: MC 5479

Abstract: Previously, we have seen a variety of approximation methods for k-median, and last week we saw that assumptions on the structure of our clustering instances can lead to better guarantees. In their work of the same title, Pranjal Awasthi, Avrim Blum, and Or Sheffet introduce the notion of weak deletion stability for k-means and k-median instances and use this assumption to obtain a PTAS.
A k-median instance is weak deletion stable if for every pair of clusters in an optimal clustering when we reassign all points in one to the other this increases the objective cost by a factor of at least (1+\alpha) for some constant \alpha > 0. I will present their algorithm, which obtains a (1 + \epsilon)-approximation for such k-median instances, and discuss how the technique is extended to k-means

Location 
MC - Mathematics & Computer Building

200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
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
3
4
  1. 2019 (167)
    1. December (5)
    2. November (15)
    3. October (18)
    4. September (15)
    5. August (9)
    6. July (17)
    7. June (18)
    8. May (16)
    9. April (9)
    10. March (24)
    11. February (13)
    12. 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)