Contact Info
Combinatorics & Optimization
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1
Phone: 519-888-4567, ext 33038
PDF files require Adobe Acrobat Reader.
Friday, October 19, 2018 1:00 PM EDT
Title: Primal-dual and Lagrangian relaxation techniques for k-median
Speaker: Madison Van Dyk Affiliation: University of Waterloo Room: MC 5479Abstract: We will develop primal-dual algorithms to obtain constant-factor approximations for the uncapacitated facility location problem.
Friday, October 19, 2018 3:30 PM EDT
Title: New algorithms for maximum disjoint paths based on tree-likeness
Speaker: Matthias Mnich Affiliation: University of Bonn Room: MC 5501Abstract:
We study the classical NP-hard problems of finding maximum-size subsets from given sets of k terminal pairs that can be routed via edge-disjoint paths (MaxEDP) or node-disjoint paths (MaxNDP) in a given graph.