Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, May 16, 2013, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Tillmann Miltzow (Freie Universität Berlin)
(joint work with Balazs Keszegh and Andrei Asinowski) We are given two sets S,T with m and n elements respectively.(m much smaller n) Every member of S has a complete preference list over the members of T. An injective mapping from S to T is an exchange stable matching if there is no other matching, where at least one member s of S is assigned to a better 'partner' and no one is assigned to a worse 'partner'. We say a member t of T can be reached if there exists an exchange stable matching containing t. We show at most O( m log(m) ) many members of T can be reached. This bound is tight.
Automatic MiSe System Software Version 1.4803M | admin login