全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...
Algorithms  2013 

Linear Time Local Approximation Algorithm for Maximum Stable Marriage

DOI: 10.3390/a6030471

Keywords: stable marriage, Gale-Shapley algorithm, approximation, Hospitals/Residents problem

Full-Text   Cite this paper   Add to My Lib

Abstract:

We consider a two-sided market under incomplete preference lists with ties, where the goal is to find a maximum size stable matching. The problem is APX-hard, and a 3/2-approximation was given by McDermid [1]. This algorithm has a non-linear running time, and, more importantly needs global knowledge of all preference lists. We present a very natural, economically reasonable, local, linear time algorithm with the same ratio, using some ideas of Paluch [2]. In this algorithm every person make decisions using only their own list, and some information asked from members of these lists (as in the case of the famous algorithm of Gale and Shapley). Some consequences to the Hospitals/Residents problem are also discussed.

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133