This talk on A 3/2-approximation algorithm for the stable marriage problem with ties was held on Wednesday October 4, 2017 in MC 4045. The talk was given by Felix Bauckholt.
Abstract
I will introduce the Stable Marriage Problem, and its NP-complete cousin, the Stable Marriage Problem with ties. I will present a simplified version of Király’s 3/2-approximation algorithm, which archieves the best approximation ratio known.
The slides for this presentation are available.