This Friday there will be another interesting algorithms talk. The speaker is Kavitha Telikepalli, who is visiting us from the Tata institute. It will be held at the usual time and place of 11am in the boardroom.
Abstract: The input is an instance of the stable marriage problem G =
(A U B, E) and the problem is to compute matchings whose size is
larger than that of a stable matching and whose “popularity” is good.
We first show a linear time algorithm for computing a maximum-size
popular matching and then generalise it to an O(km) algorithm for
computing a matching whose size is at least k/(k+1).(size of a maximum
matching in G) and whose unpopularity factor is at most k-1, for any
integer k > 1.