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, June 28, 2019 1:00 PM EDT
Title: Approximation Algorithms for the Stable Marriage Problem
Speaker: Madison Van Dyk Affiliation: University of Waterloo Room: MC 5479Abstract:
This week we will discuss stable matching when there are unacceptable pairs and preferences include ties. In this setting one can also consider the Hospitals/Residents problem and the variant where ties are one-sided.
Friday, June 28, 2019 3:30 PM EDT
Title: On the hardness of computing the diameter of a polytope
Speaker: Laura Sanita Affiliation: University of Waterloo Room: MC 5501Abstract:
The diameter of a polytope P is given by the maximum length of a shortest path between a pair of vertices on P. Giving bounds on the diameter of a polytope is a fundamental research topic in theoretical computer science and discrete mathematics, motivated by the (still unknown) existence of a polynomial pivot rule for the Simplex Algorithm for solving Linear Programs.