University COVID-19 update

The University of Waterloo is constantly updating our most Frequently Asked Questions.

Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

Tutte seminar - Deeparnab ChakrabartyExport this event to calendar

Friday, November 27, 2009 — 3:30 PM to 4:30 PM EST

Linear Programming Relaxations for Steiner Trees

Speaker: Dan McQuillan
Affiliation: Norwich University
Room: Mathematics & Computer Building (MC) 5158

Abstract:

Given a set T of terminal vertices in an undirected weighted graph, the Steiner tree problem is to find the cheapest tree containing T using possibly some other vertices of the graph. 

This problem is a classical NP-hard combinatorial optimization problems, and we are interested in designing efficient approximation algorithms. In particular, we investigate the technique of designing LP relaxations of an IP for the problem and studying their integrality gaps (the ratio of the value of the IP to the LP). 
In this talk, I will survey the various relaxations that have been studied for the problem, and point out their successes or the lack thereof in designing approximation algorithms. We will talk about old, new and fresh off the oven developments.

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