{"entities":{"Q1736562":{"pageid":1747303,"ns":120,"title":"Item:Q1736562","lastrevid":56696334,"modified":"2026-03-18T22:58:05Z","type":"item","id":"Q1736562","labels":{"en":{"language":"en","value":"Improving man-optimal stable matchings by minimum change of preference lists"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7042165"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736562$8AA50267-6311-4D1E-954C-593D591D25E1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6ed14e85a0610e641ac51219c7be2be997775aab","datavalue":{"value":{"text":"Improving man-optimal stable matchings by minimum change of preference lists","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1736562$34ABAAA4-77E9-4962-AF31-67BDED005F1B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"82d69025a7fa202df407675b6987a79a3f5c7c67","datavalue":{"value":"1461.68088","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736562$1C244CA4-F7CD-4B4F-B498-1E3D5A7B20BB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a625b6660d9638b9ced0034164298ae2932027a8","datavalue":{"value":{"entity-type":"item","numeric-id":1736560,"id":"Q1736560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736562$EA1C9623-D42A-4551-91C1-75B116BCC92D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9380ba3d7192d4700d42b0d094e27aae962de032","datavalue":{"value":{"entity-type":"item","numeric-id":314432,"id":"Q314432"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736562$395C73C2-E757-4DD0-B5EB-428EB36772A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"78a21800a31795763583b54b40324d17bf6c6658","datavalue":{"value":{"entity-type":"item","numeric-id":261377,"id":"Q261377"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736562$C26C1218-01B8-4985-A58E-A05E916DACD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a2cf34be3b1b9f51b3fff50761f97432b50aefeb","datavalue":{"value":{"entity-type":"item","numeric-id":261378,"id":"Q261378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736562$51509DFA-1961-41CD-8A67-A7FCDA3B0E6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d1ce276cd1aca185f6271fa424aa58f8f33ac0e5","datavalue":{"value":{"entity-type":"item","numeric-id":1736561,"id":"Q1736561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736562$2793CA54-24D4-4785-9468-B48B8C47A54B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"18e3aed7ec2baba1bc6b2c08988b16bb9ac0e77f","datavalue":{"value":{"entity-type":"item","numeric-id":82263,"id":"Q82263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736562$48085169-2A9D-4EBC-9EF3-ACF3CC761F89","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d660e31d569d3203bec6d5e897b7f6ed7f6a3a72","datavalue":{"value":{"time":"+2019-03-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1736562$8EB8A79F-24EC-4E28-A036-867E4C27AC8A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9b7cd2342699fb9f2413ad3e31cdc4aee476e9d3","datavalue":{"value":"Summary: In the stable marriage problem, any instance admits the so-called \\textit{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's preference list. We show that the optimization variant and the decision variant of this problem can be solved in time \\(O(n^3)\\) and \\(O(n^2)\\), 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's preference lists. We show that the problem is W[1]-hard with respect to the parameter \\(k\\) and give \\(O(n^{2k+1})\\)-time and \\(O(n^{k+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(n^{2.5}\\log n)\\)-time and \\(O(n^2)\\)-time algorithms for the optimization and decision variants, respectively.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736562$0D0EB396-3F1A-4630-9224-B69D1B562353","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736562$E9A7B6E4-DEE6-425B-BD1F-68383A7DFE60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7ddaa80bf0a693a36c1113ff6b7ad576f729940","datavalue":{"value":"68W40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736562$E28D2147-DA55-4E24-B691-BCA550E091F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736562$45630964-11F5-4490-A7EC-D847480DF9B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3a60d31ba98ba15733a78db77bf150ba7f919715","datavalue":{"value":"91B68","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736562$3D1CF5CD-D24E-47A2-A28C-12932686E95B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0669382cc3fb0ce9d3ac93874ca027efc30c0766","datavalue":{"value":"7042165","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736562$8EDA3B16-A535-40C6-BA73-C7403E04124B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c123c988a4455db85cc065f2e06e0a8051be65dd","datavalue":{"value":"combinatorial optimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736562$2383010C-7758-46A3-9AD5-F04899A3CB6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1a92166f5adeebffc8c81c6abb980ed495030be8","datavalue":{"value":"polynomial-time algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736562$B9E0279C-E83A-448A-80AC-9975BBFEF073","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"83a57ecf4aa27cc4dcc5c4ab35386a309ef35a50","datavalue":{"value":"stable marriage problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736562$DE3B4649-C62A-46BB-8341-0C8EAF3E9BA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5dccf5c44affd670167b8a549de06b9f4bbab0db","datavalue":{"value":"man-optimal stable matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736562$6C9B27A4-84FB-4F2B-AB8E-C21A7E9C0CAC","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736562$95D1BD7B-B9BC-4E06-86FF-B59D4D5D3107","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"15db416358c7bbb30be770ce30ceec54668aae3f","datavalue":{"value":"https://doi.org/10.3390/a6020371","type":"string"},"datatype":"url"},"type":"statement","id":"Q1736562$D180E95C-3CB6-4450-BFED-198EEE0A6203","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ccbb67b05981f1cce841dc7a685bd77d82b5c1e9","datavalue":{"value":"W2150787783","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736562$FC9D3381-7B22-4472-8902-B078CAD1F8B7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd41a3d3ffce78a856861213ff6553c14d782cc0","datavalue":{"value":{"entity-type":"item","numeric-id":5904119,"id":"Q5904119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736562$90C501A5-AD74-4301-9C2F-7D4E213EDAD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"79f7f06ae9524634bd51bd90fd496fbe88810422","datavalue":{"value":{"entity-type":"item","numeric-id":3995616,"id":"Q3995616"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736562$80FC5C29-5160-4346-99E2-08A511A4E768","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e32f27e3fad50fcce8692b34fdcb914afb906471","datavalue":{"value":{"entity-type":"item","numeric-id":5449547,"id":"Q5449547"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736562$A446C2A5-B32F-4FC9-BA12-585DFC88B92F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9c5b7bd3d8caab92d214aab256aced43c1dff9b","datavalue":{"value":{"entity-type":"item","numeric-id":2875146,"id":"Q2875146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736562$855F80B5-4C89-4439-A25F-67FCB00306A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9cc833c04e046c3613d9661ac4a1c39867f4a31c","datavalue":{"value":{"entity-type":"item","numeric-id":4899257,"id":"Q4899257"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736562$B1247F3E-493A-45A9-9DFA-E0AFC337AE1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc0e8163b1cc59cd0372ae78b75cdf8e0d4a3fac","datavalue":{"value":{"entity-type":"item","numeric-id":4729348,"id":"Q4729348"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736562$A50569AD-5E8E-49BC-9DC1-3991A8BF077A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"72b25ea23d21eff6a01005a0ca69d9a6f62f18c8","datavalue":{"value":"10.3390/A6020371","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736562$74FE845A-B6D1-4407-BD87-0933CABEE663","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"43b8a5ffa7e84f0a89be141a7eca6e9069c17051","datavalue":{"value":{"entity-type":"item","numeric-id":500490,"id":"Q500490"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"711868a444bffa44e864100df0e18a6ee9088fd6","datavalue":{"value":{"amount":"+0.8800943","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736562$481B13CD-4389-4524-9580-0CF6D8458D45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2bcac55b808e5add2b7758b0d7e896ff20302e36","datavalue":{"value":{"entity-type":"item","numeric-id":1736594,"id":"Q1736594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"849af155612e68cff961ded57aedd17e7ff41d58","datavalue":{"value":{"amount":"+0.87814903","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736562$9A7D6860-D082-4373-A554-CE201C708633","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e2bb9ef6e61381ed60469f8357cfd6a3081559a7","datavalue":{"value":{"entity-type":"item","numeric-id":2699977,"id":"Q2699977"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"29b9d55f2da29be927c56c082f071c6a1c358ab1","datavalue":{"value":{"amount":"+0.8766314","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736562$F354E4B9-B2AA-479E-9CF7-E9C8FFA6AECA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b57a7d0108e64aad934f3fe763be250296fe2093","datavalue":{"value":{"entity-type":"item","numeric-id":3449577,"id":"Q3449577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"16f8384275ee6951dea8e40af6590d823c56c1eb","datavalue":{"value":{"amount":"+0.8678583","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736562$5B383DDD-5F85-4829-A3ED-267C2F326984","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cd12210b6685ff1d185476683f61354ed6c8d5cd","datavalue":{"value":{"entity-type":"item","numeric-id":4305353,"id":"Q4305353"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ac476107623644bdf2a8bef2bdd2daee05abb36c","datavalue":{"value":{"amount":"+0.8663493","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736562$784B57E7-1922-4EB5-8E9D-42CAA78A760B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"da87490afaace244dc67e724c845d070560b3367","datavalue":{"value":{"entity-type":"item","numeric-id":1804884,"id":"Q1804884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4736ae70d42a03910b9258e7f1e01b5fbe2f6665","datavalue":{"value":{"amount":"+0.8602481","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736562$B7CAE574-CCB5-419A-B0EC-60C51B2C5BD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"054af94ab3e052d4e23ffe45219c7a0e6557e56b","datavalue":{"value":{"entity-type":"item","numeric-id":2078608,"id":"Q2078608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"38e573ea7f93eaf5139065ebf924368c0a68994d","datavalue":{"value":{"amount":"+0.8594347","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736562$839F9C06-CF5A-44FE-B29D-FC3140EFDEB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3466ff9ea3d17042c770a5cdacae6433a837fc6a","datavalue":{"value":{"entity-type":"item","numeric-id":2027037,"id":"Q2027037"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ff05cdee6c04b148d73f17b2c0ff0028531739ca","datavalue":{"value":{"amount":"+0.85905623","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736562$C3CB840B-A774-4D0A-9F2A-8C16BFD28B8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"48496b8c812c7624094f0755f69ec4501ade8cb7","datavalue":{"value":{"entity-type":"item","numeric-id":2896388,"id":"Q2896388"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7c8989bb8d4b038f26fec5bd753e03af0e9b9932","datavalue":{"value":{"amount":"+0.85755086","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736562$32A7DD08-30A3-4FF6-826A-6E61D480745B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4a69380a67137daaa71445eeb4da87be48d94667","datavalue":{"value":{"entity-type":"item","numeric-id":1736612,"id":"Q1736612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7c8989bb8d4b038f26fec5bd753e03af0e9b9932","datavalue":{"value":{"amount":"+0.85755086","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736562$F6FE4477-4692-4225-87FF-74F1982E7188","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736562$7CAF625A-92CA-4027-9843-CA94809A9AEE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1736562","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1736562"}}}}}