There have been 1 completed talk tagged with approximation algorithm.
A 3/2-approximation algorithm for the stable marriage problem with ties
Delivered by Felix Bauckholt on Wednesday October 4, 2017
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.