THIS SITE

Information for

Combinatorial OptimizationExport this event to calendar

Friday, October 19, 2018 — 1:00 PM EDT

Title: Primal-dual and Lagrangian relaxation techniques for k-median

Speaker: Madison Van Dyk
Affiliation: University of Waterloo
Room:  MC 5479

Abstract: We will develop primal-dual algorithms to obtain constant-factor approximations for the uncapacitated facility location problem. We will then show how Lagrangian relaxation can be used to extend these techniques for the k-median problem. This talk is based on the relevant sections of The Design of Approximation Algorithms by Shmoys and Williamson, and Approximation Algorithms for Facility Location Problems by Jens Vygen.

Location 
MC - Mathematics & Computer Building
5479
200 University Avenue West
Waterloo, ON N2L 3G1
Canada

S M T W T F S
25
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
  1. 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)
  2. 2017 (103)
    1. December (4)
    2. November (19)
    3. October (11)
    4. September (7)
    5. August (3)
    6. July (5)
    7. June (9)
    8. May (10)
    9. April (7)
    10. March (13)
    11. February (10)
    12. January (5)
  3. 2016 (137)
  4. 2015 (136)
  5. 2014 (88)
  6. 2013 (48)
  7. 2012 (39)
  8. 2011 (36)
  9. 2010 (40)
  10. 2009 (40)
  11. 2008 (39)
  12. 2007 (15)