you're reading...

Popularity vs Max-cardinality in the stable marriage setting – Kavitha Telikepalli

Dear all,

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.



No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

Enter your email address to subscribe to receive notifications of new announcements by email.

Join 68 other followers

%d bloggers like this: