Combinatorial Optimization Reading Group- Sharat ImbrahimpurExport this event to calendar

Friday, November 2, 2018 1:00 PM EDT

Title: Approximating k-Median via Pseudo-Approximation

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

Abstract: In the last two talks we saw two approaches for approximating k-median. The first approach was to use primal-dual method to approximate uncapacitated facility location and then extend this algorithm, at a loss of factor of 2, to k-median in a blackbox fashion by using the Lagrangian relaxation technique. In the second approach we saw that local search with p swaps gives a 3+2/p-approximation. For more than a decade beating the 3-approximation guarantee for k-median was considered an important open problem. In this talk I will present a 2.74-approximation algorithm for k-median based on the work of Shi Li and Ola Svensson by the same title.

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

Waterloo, ON N2L 3G1
Canada

S M T W T F S
26
27
28
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
3
4
5
6
  1. 2023 (148)
    1. December (8)
    2. November (17)
    3. October (14)
    4. September (10)
    5. August (7)
    6. July (19)
    7. June (21)
    8. May (12)
    9. April (5)
    10. March (17)
    11. February (10)
    12. January (8)
  2. 2022 (150)
    1. December (8)
    2. November (18)
    3. October (15)
    4. September (11)
    5. August (2)
    6. July (17)
    7. June (17)
    8. May (10)
    9. April (12)
    10. March (18)
    11. February (10)
    12. January (13)
  3. 2021 (103)
  4. 2020 (119)
  5. 2019 (167)
  6. 2018 (136)
  7. 2017 (103)
  8. 2016 (137)
  9. 2015 (136)
  10. 2014 (88)
  11. 2013 (48)
  12. 2012 (39)
  13. 2011 (36)
  14. 2010 (40)
  15. 2009 (40)
  16. 2008 (39)
  17. 2007 (15)