Authors: Kazuo Iwama Shuichi Miyazaki Hiroki Yanagisawa
Publish Date: 2012/10/18
Volume: 68, Issue: 3, Pages: 758-775
Abstract
The problem of finding a largest stable matching where preference lists may include ties and unacceptable partners MAX SMTI is known to be NPhard It cannot be approximated within 33/29 11379 unless P=NP and the current best approximation algorithm achieves the ratio of 15 MAX SMTI remains NPhard even when preference lists of one side do not contain ties and it cannot be approximated within 21/19 11052 unless P=NP However even under this restriction the best known approximation ratio is still 15 In this paper we improve it to 25/17 14706
Keywords: