The F2018 Round 2 SASMS will be held on Tuesday, November 13 at 18:00 in MC 5479. If you would like to give a talk, you may do so by clicking "Sign Up" above.

18:00

18:30

Pure Math Club

Dinner

19:00

Stephen Charles Zheng Biao Wen

Cooperation

19:30

Adam John Michael Brown

Three proofs of Koenig's Lemma

20:00

Zishen Qu

An Approximation Algorithm for the k-centre Problem

20:30

We examine concepts of cooperative games in the context of a three player voting game where one player has a veto. We will introduce the core, the von Neumann-Morgenstern stable set, and the Ray-Vohra farsighted stable set.

Using LP duality, matroid intersection, and max-flow min-cut.

We will show that there is a polynomial time 2-approximation to the metric k-centre problem, and that this result cannot be improved given that the polynomial time complexity class is strictly contained in the non-deterministic polynomial time complexity class.