Modeling UpLink power control with outage probabilities
Kenneth L. Clarkson, K. Georg Hampel, et al.
VTC Spring 2007
The problem of finding a largest stable matching where preference lists may include ties and unacceptable partners (MAX SMTI) is known to be NP-hard. It cannot be approximated within 33/29 (>1.1379) unless P=NP, and the current best approximation algorithm achieves the ratio of 1.5. MAX SMTI remains NP-hard even when preference lists of one side do not contain ties, and it cannot be approximated within 21/19 (>1.1052) unless P=NP. However, even under this restriction, the best known approximation ratio is still 1.5. In this paper, we improve it to 25/17 (<1.4706). © 2012 Springer Science+Business Media New York.
Kenneth L. Clarkson, K. Georg Hampel, et al.
VTC Spring 2007
S.F. Fan, W.B. Yun, et al.
Proceedings of SPIE 1989
F. Odeh, I. Tadjbakhsh
Archive for Rational Mechanics and Analysis
Satoshi Hada
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences