Reasoning about RoboCup soccer narratives
Hannaneh Hajishirzi, Julia Hockenmaier, et al.
UAI 2011
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.
Hannaneh Hajishirzi, Julia Hockenmaier, et al.
UAI 2011
Trang H. Tran, Lam Nguyen, et al.
INFORMS 2022
D.S. Turaga, K. Ratakonda, et al.
SCC 2006
Ronen Feldman, Martin Charles Golumbic
Ann. Math. Artif. Intell.