Approximation algorithm

There have been 1 completed talk tagged with approximation algorithm.

Related Tags

• stable marriage problem
• matching
• optimization
• graph theory
• algorithm
• combinatorics
• computer science

Completed Talks

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.