Tutte seminar - Zachary FriggstadExport this event to calendar

Friday, June 29, 2012 — 3:30 PM to 4:30 PM EDT

Approximating Minimum Cost Connected T-Joins

Speaker: Zachary Friggstad
Affiliation: University of Waterloo
Room: Mathematics & Computer Building (MC) 5158

Abstract:

Given a graph G and a subset of nodes T, a connected T-join is a connected spanning subgraph H such that T is exactly the set of even-degree nodes; H may have multiple copies of any edge of G. If the edges of G have weights, it is natural to consider the problem of finding the minimum weight connected T-join in G. This generalizes the notion of the classic traveling salesman problem (T = {}) and its path variant (T = {s,t}).

As with TSP paths, it is relatively easy to get a 5/3-approximation for the connected T-join problem. We generalize recent results by An, Kleinberg, and Shmoys on TSP paths and obtain an approximation algorithm for the connected T-join problem that finds a solution of cost at most 261/160 = 1.63125 times the cost of the optimum solution. We also show that this analysis can be improved when the size of T is bounded by a constant. Finally, we present a 3-approximation for a prize-collecting variant of the problem where we are allowed exclude some nodes from the connected T-join by paying some penalty.

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

Waterloo, ON N2L 3G1
Canada

S M T W T F S
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
1
2
  1. 2021 (102)
    1. December (2)
    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)