Friday, January 28, 2022

Friday, January 28, 2022 — 3:30 PM EST

Title: Traveling Salesman Problems: Approximation Algorithms and Black-Box Reductions

Speaker: Jens Vygen Affiliation: University of Bonn Zoom: Please email Emma Watson

Abstract:

We survey the recent progress on approximation algorithms and integrality ratios for variants of the traveling salesman problem, with a focus on black-box reductions from one problem to another. In particular, we explain recent results for the Path TSP and the Capacitated Vehicle Routing Problem, which are joint works with Vera Traub and Rico Zenklusen and with Jannis Blauth and Vera Traub.

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