There have been 1 completed talk tagged with matching.
- approximation algorithm
- stable marriage problem
- graph theory
- computer science
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.