{"entities":{"Q1736612":{"pageid":1747353,"ns":120,"title":"Item:Q1736612","lastrevid":72381444,"modified":"2026-04-14T04:31:21Z","type":"item","id":"Q1736612","labels":{"en":{"language":"en","value":"Faster and simpler approximation of stable matchings"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7042201"}},"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":"Q1736612$739FF2B5-2FAF-402C-8C0B-7896521725B3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4758824967746b882223aa04f4521ceef99cfed4","datavalue":{"value":{"text":"Faster and simpler approximation of stable matchings","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1736612$23BA33E5-6E80-4ECC-B659-B0CC2EC02F53","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c7360147152e614ca93f365b9499f1fa13dcc2f8","datavalue":{"value":"1461.68259","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736612$BB0631D3-E291-44F3-83CF-789EBD550262","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":"Q1736612$0E8D16BC-A225-41FE-8CA7-2D29E8A8B8E7","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":"Q1736612$343D073A-A0D7-4DDD-BA6F-819C6824539B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b254314a294309ae4f0067b1a390addb223dd835","datavalue":{"value":"Summary: We give a \\(\\frac{3}{2}\\)-approximation algorithm for finding stable matchings that runs in \\(O(m)\\) time. The previous most well-known algorithm, by McDermid, has the same approximation ratio but runs in \\(O(n^{3 / 2} m)\\) time, where \\(n\\) denotes the number of people and \\(m\\) is the total length of the preference lists in a given instance. In addition, the algorithm and the analysis are much simpler. We also give the extension of the algorithm for computing stablemany-to-many matchings.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736612$39CE10A6-3A7D-4426-B25A-02099A50C5A4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736612$0C5FF06F-A0F0-4EBE-87FB-39BDA408CF0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736612$65252DE3-38E0-40DB-9582-CC07F53B053D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3a60d31ba98ba15733a78db77bf150ba7f919715","datavalue":{"value":"91B68","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736612$30F9CC0B-D63D-471F-BFCC-36E761DE3977","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"388519819139f3a0823b4b6ee93cc96e2b770e70","datavalue":{"value":"7042201","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736612$B09CDF46-4E6A-4EBA-97B3-EFA759811267","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"05d75808b9d7c13ab094522d6fcf62cca5459868","datavalue":{"value":"stable matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736612$4A9742B9-577C-4DF8-9375-07BC4D113129","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ddbc37dabc8b8e14a2e4ff24e3be90ca98bbadd7","datavalue":{"value":"stable marriage","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736612$FA050BE4-1D83-45C1-94DC-63908194A489","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0de600cf8191fa1f423fd01c9a02b172072a7391","datavalue":{"value":"approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736612$6D088B7E-3EA0-43AE-8F8B-DA5BBFABA6DC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"fe31a2aa7d8847b53f6515e8866194b269d2799a","datavalue":{"value":{"entity-type":"item","numeric-id":1006381,"id":"Q1006381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736612$2CC5AF78-2C70-4367-8033-2AD97A2604F8","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":"Q1736612$7C961381-7D61-474B-AC1B-D187B666E0A3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b7384b0abe172ce1190c0e35bc03a14c5e68c15f","datavalue":{"value":"https://doi.org/10.3390/a7020189","type":"string"},"datatype":"url"},"type":"statement","id":"Q1736612$8F29A039-F836-4C01-BC17-32FD9B7ABED4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"64e1947fe83a61304eddaeedb3c30dca9a71d7b4","datavalue":{"value":"W2019340823","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736612$6DAB1648-E77E-4D25-9CF7-4D4B23F5AFB7","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":"Q1736612$C5A5BAC1-6E0E-4A46-8130-E81CE7961602","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63aa60b1456767d5f4928fecf9ef6b9d0864b8f9","datavalue":{"value":{"entity-type":"item","numeric-id":1426466,"id":"Q1426466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736612$2BA533F5-9698-429C-876D-12FC25F73EDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d7bb75e607bd7a043bb2e5aa64550ecbb684d85a","datavalue":{"value":{"entity-type":"item","numeric-id":3580942,"id":"Q3580942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736612$3D85DAD4-99F9-4257-907F-78BB14A0C9DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f3a326e7002e489bc9b030d4d456ce02b2acf1b6","datavalue":{"value":{"entity-type":"item","numeric-id":5406194,"id":"Q5406194"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736612$282287EB-C11F-422A-87C5-040573BB9243","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b96f254963a0a524ae51064dd44ea4bc44f0a0f1","datavalue":{"value":{"entity-type":"item","numeric-id":930600,"id":"Q930600"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736612$F47F9A2C-A13E-4ACD-8A49-98C48478D6CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"efcc9a9bbbfd118c63bfec31d553f24636bf6cc8","datavalue":{"value":{"entity-type":"item","numeric-id":2934607,"id":"Q2934607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736612$41F7E86C-3CC8-41A6-BEAC-F55AA26869BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84c64f3b7727c1a7ae92cc24492d1135ec3f7679","datavalue":{"value":{"entity-type":"item","numeric-id":3586389,"id":"Q3586389"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736612$8B0FD273-5939-422E-B495-BEF272F6B007","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"64a48f5e48a17467d43410e6e7da6e652558acf7","datavalue":{"value":{"entity-type":"item","numeric-id":547284,"id":"Q547284"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736612$99F714A8-B064-4AB2-BA0D-E881C83ED9A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c4ed37801441b8e26b2b41f5f918dc9036ac26b","datavalue":{"value":{"entity-type":"item","numeric-id":3395507,"id":"Q3395507"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736612$50E17207-7C4D-4943-980A-AE51FEEE4E4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"349a79ba254311c619a204f46fda0f6e8e732405","datavalue":{"value":{"entity-type":"item","numeric-id":1605313,"id":"Q1605313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736612$72E4FDEF-67BE-4FA9-AD4D-9F3ADC96D53F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"30a53b4932541f0d7f382aa014da2b3225338d1d","datavalue":{"value":{"entity-type":"item","numeric-id":3638073,"id":"Q3638073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736612$76CAF6B9-C9BF-4C04-96B5-DCFF2ECFFB5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"16d8b6db9ee5c82356bbbaec73381572e840a567","datavalue":{"value":{"entity-type":"item","numeric-id":2896388,"id":"Q2896388"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736612$40A74E79-D76E-4FD9-B9C3-8528D97F0925","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56949ace75edebf8b0a7798b69da05d183592e58","datavalue":{"value":{"entity-type":"item","numeric-id":3603527,"id":"Q3603527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736612$D7F3F40E-AA96-4991-B658-284433B08EB5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a04c023055fe5b345910a608f7808e74e8076e46","datavalue":{"value":"10.3390/A7020189","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736612$DEE04432-16E6-4A6B-BFF2-5D6E10709559","rank":"normal"}],"P1643":[{"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":"1f5bad60f5d71e07f84653e70422d32de406082f","datavalue":{"value":{"amount":"+1.0","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736612$93829159-8CB3-44A4-8AB7-8ADA3270A73F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f7f46a3bc6a6818adade9ad77efb274a8a6fb438","datavalue":{"value":{"entity-type":"item","numeric-id":2796247,"id":"Q2796247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6901e5bead714f18869bf06b347c1308e2796ef6","datavalue":{"value":{"amount":"+0.9403024","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736612$F1BC40C1-69DD-4B87-92DB-69DE71869072","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c038163fcba488b04d61c08a91f41aeeeb06bb33","datavalue":{"value":{"entity-type":"item","numeric-id":3452763,"id":"Q3452763"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4fc85597bcffdfbe2cb551d4b2c5635c233e9380","datavalue":{"value":{"amount":"+0.93691903","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736612$B3D56D20-DC74-454D-8EE0-E568F3018A13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"945ca436c47f91c5da6257186edac509dad47530","datavalue":{"value":{"entity-type":"item","numeric-id":989570,"id":"Q989570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fe5bc32ee8373448530e3363a30145789f86c3ab","datavalue":{"value":{"amount":"+0.93335336","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736612$17F77269-2BDE-401D-9AF6-A5B171BB4480","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0764a5e340c92d2c1eda0b5245d25ef5bc6434b1","datavalue":{"value":{"entity-type":"item","numeric-id":2294060,"id":"Q2294060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e0fe2754d0a2b4d78290aa8c3c22a961cb46315","datavalue":{"value":{"amount":"+0.9324144","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736612$27404BA1-C5A1-4FDE-8C2C-01302BD5F5F6","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":"e4c7b5e3eda41dce67c4f658a110174180975045","datavalue":{"value":{"amount":"+0.9281665","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736612$C86A74AA-C3C6-430E-8A18-C1A971C4171E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df15cd9997902c1a8249d969d470c4311b083800","datavalue":{"value":{"entity-type":"item","numeric-id":547284,"id":"Q547284"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5b713711e7ebf520eca897b1cc5a9d8c8d63b118","datavalue":{"value":{"amount":"+0.9266291","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736612$930C281D-C098-407F-910D-3A484D0E57FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a07de26246df5546d5168b3edd43005b0d2315a2","datavalue":{"value":{"entity-type":"item","numeric-id":3541122,"id":"Q3541122"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5b713711e7ebf520eca897b1cc5a9d8c8d63b118","datavalue":{"value":{"amount":"+0.9266291","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736612$2960563E-154F-4142-B8C2-386722B6631E","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":"8a4419e8f900a8308b2bc02f6161518f8846fb12","datavalue":{"value":{"amount":"+0.92545193","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736612$F72D8D28-BE92-480B-8EDD-D14CBE809E47","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":"Q1736612$810D7959-0EFC-464A-85C2-8E47F6D14DD9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Faster and simpler approximation of stable matchings","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Faster_and_simpler_approximation_of_stable_matchings"}}}}}