Tutte seminar - Zachary FriggstadExport this event to calendar

Friday, December 9, 2011 — 3:30 PM to 4:30 PM EST

Multiple Traveling Salesmen in Asymmetric Metrics

Speaker: Levent Tunçel
Affiliation: University of Waterloo
Room:

Mathematics & Computer Building (MC) 5158

Abstract:

Consider the problem of finding k paths of minimum total cost whose union covers all nodes in a asymmetric metric graph. When k=1, this is exactly the asymmetric traveling salesman path problem. I will present a bicriteria approximation algorithm that finds up to k + k/b paths with total cost at most O(b log n) times the optimum cost of using exactly k paths where b is an input parameter and n is the number of nodes. Setting b = 1 yields an O(log n) approximation using up to 2k paths and setting b = k+1 is a true O(k log n) approximation using exactly k paths. The approximation guarantee can be stated with respect to an LP relaxation of the problem. This approach generalizes to instances where the start and end nodes of the k paths are specified in advance provided that all start nodes are the same or all end nodes are the same. I will show that the most general case when all start and end nodes may be distinct cannot be approximated within any bounded ratio unless P = NP.

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

Waterloo, ON N2L 3G1
Canada

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