Almost stable matchings in constant time

Details Almost stable matchings in constant time Almost stable matchings in constant time

2008-12-29

arxiv.org/abs/0812.4893v1

Computer Science

Data Structures and Algorithms

20 pages

Scientific paper

We show that the ratio of matched individuals to blocking pairs grows linearly with the number of propose--accept rounds executed by the Gale--Shapley algorithm for the stable marriage problem. Consequently, the participants can arrive at an almost stable matching even without full information about the problem instance; for each participant, knowing only its local neighbourhood is enough. In distributed-systems parlance, this means that if each person has only a constant number of acceptable partners, an almost stable matching emerges after a constant number of synchronous communication rounds. This holds even if ties are present in the preference lists. We apply our results to give a distributed $(2+\epsilon)$-approximation algorithm for maximum-weight matching in bicoloured graphs and a centralised randomised constant-time approximation scheme for estimating the size of a stable matching.

Affiliated with

Also associated with

No associations

Rating

Almost stable matchings in constant time does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Almost stable matchings in constant time, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Almost stable matchings in constant time will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-448616