A ( 
link.lib.tsinghua.edu.cn/media/images/contributions/7/0/6/8/70686788721N21Q4_html/MediaObjects/InlineFigure1.png" alt="MediaObjects/InlineFigure1.png" align="m
| 详细信息 | 推荐本文 | |
- 作者：Kazuo Iwama ; Shuichi Miyazaki ; Naoya Yamauchi
- 刊名：Lecture Notes in Computer Science
- 出版时间：2005
- 出版年：2005
- 期刊代码：99_0302-9743
- 类别：cp
- 卷：3827
- 期：1
- 页码：pp.902-914
- 数据来源：sp
摘要
We consider the problem of finding a stable matching of maximum size when both ties and unacceptable partners are allowed in preference lists. This problem is NP-hard and the current best known approximation algorithm achieves the approximation ratio link.lib.tsinghua.edu.cn/media/images/contributions/7/0/6/8/70686788721N21Q4_html/MediaObjects/InlineFigure2.png" alt="MediaObjects/InlineFigure2.png" align="middle">, where c is an arbitrary positive constant and N is the number of men in an input. In this paper, we improve the ratio to link.lib.tsinghua.edu.cn/media/images/contributions/7/0/6/8/70686788721N21Q4_html/MediaObjects/InlineFigure3.png" alt="MediaObjects/InlineFigure3.png" align="middle">, where c is a constant such that link.lib.tsinghua.edu.cn/media/images/contributions/7/0/6/8/70686788721N21Q4_html/MediaObjects/InlineFigure4.png" alt="MediaObjects/InlineFigure4.png" align="middle">.