Title: Approximation Algorithms for the Stable Marriage ProblemSpeaker: Madison Van Dyk Affiliation: University of Waterloo Room: MC 5479
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.
Title: On the hardness of computing the diameter of a polytopeSpeaker: Laura Sanita Affiliation: University of Waterloo Room: MC 5501
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.