TY  -  
T1  - Almost Stable Matchings by Truncating the Gale–Shapley Algorithm 
SN  -  /  
UR  - http://hdl.handle.net/10138/27920 
T3  -  
A1  - Floréen, Patrik; Kaski, Petteri; Polishchuk, Valentin; Suomela, Jukka 
A2  -  
PB  -  
Y1  - 2010 
LA  - eng 
AB  - 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 part... 
VO  -  
IS  -  
SP  -  
OP  -  
KW  - 111 Mathematics 
N1  -   
PP  -  
ER  -