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 - Andreas FeldmannExport this event to calendar

Friday, April 11, 2014 — 3:30 PM EDT

On the Equivalence of the Bidirected and Hypergraphic Relaxations for Steiner Tree

Speaker: Andreas Feldmann
Affiliation: University of Waterloo
Room: Mathematics and Computer Building (MC) 5158

Abstract: 

The bottleneck of the currently best known approximation algorithms for the NP-hard Steiner tree problem is the solution of its large, so called hypergraphic, linear programming relaxation (HYP). Hypergraphic LPs are NP-hard to solve exactly, and it is a formidable computational task to even approximate them sufficiently well.

We focus on another well-studied but poorly understood LP relaxation of
the problem: the bidirected cut relaxation (BCR). This LP is compact,
and can therefore be solved efficiently. Its integrality gap is known to
be greater than 1.161, and while this is widely conjectured to be close
to the real answer, only a (trivial) upper bound of two is known.

We give an efficient constructive proof that BCR and HYP are
polyhedrally equivalent in instances that do not have an (edge-induced)
claw on Steiner vertices; i.e., instances that do not contain a Steiner
vertex with 3 Steiner neighbours. This is a significant step forward
from the previously known equivalence for (so called quasi-bipartite)
instances in which Steiner vertices form an independent set.

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 (84)
    1. October (1)
    2. September (7)
    3. August (7)
    4. July (10)
    5. June (12)
    6. May (7)
    7. April (9)
    8. March (13)
    9. February (8)
    10. 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)