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 - Jochen KönemannExport this event to calendar

Friday, July 17, 2009 — 3:30 PM to 4:30 PM EDT

On Generalizations of Network Design Problems with Degree Bounds

Speaker: Jochen Könemann
Affiliation: Norwich University
Room: Mathematics & Computer Building (MC) 5158

Abstract:

Iterative rounding and relaxation have arguably become the method of choice in dealing with unconstrained and constrained network design problems. Starting with Jain's elegant iterative rounding scheme for the generalized Steiner network problem, the technique has more recently lead to breakthrough results in the area of constrained network design, where a number of linear constraints are added to a classical network design problem. Most notable among recent successes is Singh & Lau's +1-algorithm [STOC, 2007] for the minimum-cost degree-bounded spanning tree problem. 

In this talk we further extend the scope of the iterative relaxation method in two ways: (1) by handling more complicated degree constraints in the minimum spanning tree problem, and (2) by incorporating `degree bounds' in other combinatorial optimization problems such as matroids, matroid intersection and lattice polyhedra.
Much of the talk will focus on (1). We consider the minimum crossing spanning tree (MCST) problem, where we are given an undirected, weighted graph, vertex sets S_1,...,S_k and degree bounds b_1,...,b_k. The goal is to find a mincost spanning tree in G that has at most b_i edges crossing S_i for all i. This problem generalizes the mincost degree-bounded spanning tree problem considered Singh & Lau. We consider the special case of the problem where the given vertex sets form a laminar family, and show that the additional structure of the cuts can be used to yield improved approximation algorithms.

This is joint work with N. Bansal, R. Khandekar, V. Nagarajan & B. Peis.

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

Waterloo, ON N2L 3G1
Canada

S M T W T F S
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
  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)