{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:31:13Z","timestamp":1760243473613,"version":"build-2065373602"},"reference-count":7,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2013,5,28]],"date-time":"2013-05-28T00:00:00Z","timestamp":1369699200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>In the stable marriage problem, any instance admits the so-called man-optimal stable matching, in which every man is assigned the best possible partner. However, there are instances for which all men receive low-ranked partners even in the man-optimal stable matching. In this paper we consider the problem of improving the man-optimal stable matching by changing only one man\u2019s preference list. We show that the optimization variant and the decision variant of this problem can be solved in time O(n3) and O(n2), respectively, where n is the number of men (women) in an input. We further extend the problem so that we are allowed to change k men\u2019s preference lists. We show that the problem is W[1]-hard with respect to the parameter k and give O(n2k+1)-time and O(nk+1)-time exact algorithms for the optimization and decision variants, respectively. Finally, we show that the problems become easy when k = n; we give O(n2.5 log n)-time and O(n2)-time algorithms for the optimization and decision variants, respectively.<\/jats:p>","DOI":"10.3390\/a6020371","type":"journal-article","created":{"date-parts":[[2013,5,28]],"date-time":"2013-05-28T12:17:33Z","timestamp":1369743453000},"page":"371-382","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Improving Man-Optimal Stable Matchings by Minimum Change of Preference Lists"],"prefix":"10.3390","volume":"6","author":[{"given":"Takao","family":"Inoshita","sequence":"first","affiliation":[{"name":"Graduate School of Informatics, Kyoto University, Yoshida-honmachi, Sakyo-ku, Kyoto 606-8501, Japan"}]},{"given":"Robert","family":"Irving","sequence":"additional","affiliation":[{"name":"School of Computing Science, University of Glasgow, Glasgow, G12 8QQ, Scotland"}]},{"given":"Kazuo","family":"Iwama","sequence":"additional","affiliation":[{"name":"Graduate School of Informatics, Kyoto University, Yoshida-honmachi, Sakyo-ku, Kyoto 606-8501, Japan"}]},{"given":"Shuichi","family":"Miyazaki","sequence":"additional","affiliation":[{"name":"Academic Center for Computing and Media Studies, Kyoto University, Yoshida-honmachi, Sakyo-ku, Kyoto 606-8501, Japan"}]},{"given":"Takashi","family":"Nagase","sequence":"additional","affiliation":[{"name":"Communication Service Group, Research and Development Center, Nippon Telegraph and Telephone West Corporation, 1-2-31 Sonezaki Kita-ku Osaka 530-0057, Japan"}]}],"member":"1968","published-online":{"date-parts":[[2013,5,28]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1080\/00029890.1962.11989827","article-title":"College admissions and the stability of marriage","volume":"69","author":"Gale","year":"1962","journal-title":"Am. Math. Mon."},{"key":"ref_2","unstructured":"Gusfield, D., and Irving, R.W. (1989). The Stable Marriage Problem: Structure and Algorithms, MIT Press."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Huang, C.-C. (2006, January 11\u201313). Cheating by Men in the Gale-Shapley Stable Matching Algorithm. Proceedings of the ESA 2006, Zurich, Switzerland.","DOI":"10.1007\/11841036_39"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Bhaskara, A., Charikar, M., Chlamtac, E., Feige, U., and Vijayaraghavan, A. (2010, January 5\u20138). Detecting High Log-densities\u2013an O(n1\/4) Approximation for Densest k-Subgraph. Proceedings of the STOC 2010, Cambridge, USA.","DOI":"10.1145\/1806689.1806719"},{"key":"ref_5","first-page":"242","article-title":"Finding dense subgraphs of sparse graphs","volume":"7535","author":"Komusiewicz","year":"2012","journal-title":"Proc. IPEC 2012"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Burkard, R., Dell\u2019Amico, M., and Martello, S. (2008). Assignment Problems, SIAM.","DOI":"10.1137\/1.9780898717754"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1013","DOI":"10.1137\/0218069","article-title":"Faster scaling algorithms for network problems","volume":"18","author":"Gabow","year":"1989","journal-title":"SIAM J. Comput."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/6\/2\/371\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T21:47:01Z","timestamp":1760219221000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/6\/2\/371"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,5,28]]},"references-count":7,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2013,6]]}},"alternative-id":["a6020371"],"URL":"https:\/\/doi.org\/10.3390\/a6020371","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2013,5,28]]}}}