Tutte seminar - Takuro FukunagaExport this event to calendar

Friday, April 27, 2012 — 3:30 PM to 4:30 PM EDT

Iterative rounding approximation algorithms for degree-bounded node-connectivity network design

Speaker: Takuro Fukunaga
Affiliation: Kyoto University
Room: Mathematics & Computer Building (MC) 5158

Abstract:

We consider the problem of finding a minimum edge cost subgraph of an undirected or a directed graph satisfying given connectivity requirements and degree bounds b on nodes. We present an iterative rounding algorithm of the set-pair LP relaxation for this problem. When the graph is undirected and the connectivity requirements are on the element-connectivity with maximum value k, our algorithm computes a solution that is an O(k)-approximation for the edge cost in which the degree of each node v is at most O(k)b(v). We also consider the no edge cost case where the objective is to find a subgraph satisfying connectivity requirements and degree bounds. Our algorithm for this case outputs a solution in which the degree of each node v is at most 6b(v) + O(k^2). These algorithms can be extended to other well-studied undirected node-connectivity requirements such as spanning-, subset- and root-connectivity. When the graph is directed and the connectivity requirement is spanning k-out-connectivity from a root, our algorithm computes a solution that is a 2-approximation for the edge cost in which the degree of each node v is at most 2b(v) + O(k).

This is a joint work with R. Ravi (CMU).

Location 
MC - Mathematics & Computer Building
5158
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. 2021 (95)
    1. November (2)
    2. October (6)
    3. September (12)
    4. August (6)
    5. July (10)
    6. June (12)
    7. May (7)
    8. April (9)
    9. March (13)
    10. February (8)
    11. 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)