{"entities":{"Q1062912":{"pageid":1073664,"ns":120,"title":"Item:Q1062912","lastrevid":66177288,"modified":"2026-04-12T08:04:01Z","type":"item","id":"Q1062912","labels":{"en":{"language":"en","value":"An analysis of a decomposition heuristic for the assignment problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3916021"}},"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":"Q1062912$D4698D4C-9773-409C-A672-030787EA9AF4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6e70691d2f5a73f58cb3936cb47ffbf0e47187b7","datavalue":{"value":{"text":"An analysis of a decomposition heuristic for the assignment problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1062912$BBAFB4B3-65B1-40FE-B67E-6D9F8058E03F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"96de78e16a811ef47dd47654e4171d4e44d7b118","datavalue":{"value":"0573.90069","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062912$F2AE8AC1-FA05-48DF-98E7-5814F7132568","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"cba16d423e5677caf8cc93f204fcf1cc5fc6162c","datavalue":{"value":"10.1016/0167-6377(85)90001-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062912$BB9B82C0-9B1A-4026-A899-B31D50D675D5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8f80dfc7d569f12c09d99bcc3b3496b227a33b7d","datavalue":{"value":{"entity-type":"item","numeric-id":173840,"id":"Q173840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062912$E5B3AB9B-45C6-4C3F-B5B5-1AF42F4868ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"68ee3d60719c97b3f7244d7f2c477985e89e7464","datavalue":{"value":{"entity-type":"item","numeric-id":1242411,"id":"Q1242411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062912$5C9F3ED6-2B8A-4C7C-8C13-CEA60F9D9813","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f9747a37b0b56aeca2085282046e2737cd5087ca","datavalue":{"value":{"entity-type":"item","numeric-id":96289,"id":"Q96289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062912$EF1C6292-8978-4DC6-A57E-A3B80340DB34","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1062912$1E898347-1983-45FA-A5DF-3261F6CD29B7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bccfb325f24786e306ac38a8cf11401968cb4791","datavalue":{"value":"\\textit{J. M. Kurtzberg} [J. Assoc. Comput. Mach. 9, 419-439 (1962; Zbl 0108.333)] proposed a method of obtaining approximate solutions to the assignment problem by decomposing a large problem into many smaller subproblems. Thus a km\\(\\times km\\) assignment problem is decomposed into \\(k^ 2\\) problems of size \\(m\\times m\\) and one problem of size \\(k\\times k\\). In this paper we analyze the performance of this heuristic, obtaining the following main results: (1) For the maximization problem, the ratio of the optimal solution to the heuristic solution can be as large as, but cannot exceed min(k,m); (2) For the minimization problem, if \\(k=O(n/\\log n)\\) where \\(n=mk\\), and the matrix elements are independently drawn from a uniform distribution on (0,1), in the limit the expected value of the heuristic solution is at least k/3 times that of the optimal solution.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062912$9F61F42C-66E4-40F6-B0F9-93730DB2B66C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"63b70ec5cb69f5c5c9550409918141ca28bfae61","datavalue":{"value":"90C08","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062912$07CB35E1-A1B2-4070-8171-141BC2AD5BDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062912$51EE2F80-8080-4CE0-AFB4-B86DD75419B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062912$0333C554-BB1B-4C51-AF7A-26F4CCCED6D3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"897003d795a04c05e46d49d2fb6b82908ced8d4d","datavalue":{"value":"3916021","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062912$4BF76C9D-3D90-4877-B41F-65D671F1E278","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3d2e2522be9551d10b087fdba2d198c51773b780","datavalue":{"value":"performance analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062912$07CF336D-E2ED-445B-8029-B56A98CFEB47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"90bc349d6d55eb8026148892e900ce256ffdd986","datavalue":{"value":"analysis of algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062912$604E6CBD-4DCD-45D8-94DD-F4ADC3FC6DD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"615f2a3773e3a9a3bad386a540fbc6c58cfa22ee","datavalue":{"value":"decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062912$F596FC85-F78B-4119-A9BF-FED6766CA386","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8205005c0975ece57da73400ce9be01687bc47fd","datavalue":{"value":"approximate solutions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062912$65B91CA2-0187-4161-A643-E34AA58F51A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9374ed2d3172dd37d5ebf823ec4347cfa78fc4b7","datavalue":{"value":"assignment problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062912$A471B673-CE33-4972-AA0B-4A50F35A6120","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"42c07d7d08037b37637b1f2ab07f3138ef866264","datavalue":{"value":"heuristic solution","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062912$8DCBAC48-5C67-439F-92F8-9CD4026A816E","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":"Q1062912$E3089E09-F4C0-4806-B232-C0E0B4560222","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d99b6b1510cc48c01add15e4d9b0ddec53d7dad","datavalue":{"value":{"entity-type":"item","numeric-id":3315292,"id":"Q3315292"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062912$77E60D6D-1590-4EAA-921A-8C2E99F6F052","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"491114bf078fcb4fbdf112a6c375b2016fcc2e7c","datavalue":{"value":{"entity-type":"item","numeric-id":1154740,"id":"Q1154740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062912$4D5FF2B3-AB9A-4C64-95B0-3A655664D12A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b5085f3bf4f6355e1ff1056e92d202dd1c1f523","datavalue":{"value":{"entity-type":"item","numeric-id":3844783,"id":"Q3844783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062912$05B82420-23E4-4130-8760-4D3DB55DD595","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b550c6aeb9cd2559d0d5cc7f2588df3db64a8a1","datavalue":{"value":{"entity-type":"item","numeric-id":3796776,"id":"Q3796776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062912$F8680815-3EE2-45CE-B726-FE54683083AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ad86ed10f9dbc91aef6fdb78e5f6edf0ab2f5e6","datavalue":{"value":{"entity-type":"item","numeric-id":4739657,"id":"Q4739657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062912$51E77869-AD30-438F-8DEA-ACDEA9855F42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"046e9440c3df548a174bc6cde28627a144dc8011","datavalue":{"value":{"entity-type":"item","numeric-id":3048272,"id":"Q3048272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062912$E8C4C566-927F-4F58-A453-00D5CBA6167C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"feb8c5cbab981c46929a2d57d1fdf3a9a0b66bfd","datavalue":{"value":"https://doi.org/10.1016/0167-6377(85)90001-x","type":"string"},"datatype":"url"},"type":"statement","id":"Q1062912$9F557736-B033-4203-B5AB-BD5ABD94AE07","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8fdbbb0a4436f1f20e76f146dad6ba163ad5f298","datavalue":{"value":"W2049737014","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062912$E874EE8B-A1E5-453E-B03D-D5B9E956FFB4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"370c2d240a2c10db0d3ddce0f87941656aac2f46","datavalue":{"value":{"entity-type":"item","numeric-id":3796776,"id":"Q3796776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"76eec7730c37cce2eb1930158d9fbb03271d65d0","datavalue":{"value":{"amount":"+0.8684495687484741","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1062912$A1C18952-F63A-4638-A126-1AD5577EDD71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e4543fabe4466e40d7467d9df9e1c78b050fa60b","datavalue":{"value":{"entity-type":"item","numeric-id":1118529,"id":"Q1118529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5cc5619bba6c53644fd8350425f2d4840786b792","datavalue":{"value":{"amount":"+0.8379113674163818","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1062912$91BC8A55-9C13-4A0C-98EE-CFCFCA34CCA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"71729eff0ad8af06276f3340f2a64b7606d2523a","datavalue":{"value":{"entity-type":"item","numeric-id":1327216,"id":"Q1327216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ae3d62e6fbe41f54acbbc08224ea72ff9c1ed783","datavalue":{"value":{"amount":"+0.8009765148162842","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1062912$56C450DD-9B53-4F64-A327-CF0D72473B92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2c9a75828e07ba213e733c4e66109bedc29c70b5","datavalue":{"value":{"entity-type":"item","numeric-id":4316542,"id":"Q4316542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d4835a97906605f4baa4e28c77b274a439130418","datavalue":{"value":{"amount":"+0.8008012771606445","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1062912$A451CB35-8E95-412E-A2A1-7B6D4BDE1098","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9bcd73a15f995c1fca59ada554e814ac9ac5f506","datavalue":{"value":{"entity-type":"item","numeric-id":3115263,"id":"Q3115263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e15a7907a362770a1e88b5113df55a8bc8b3ae33","datavalue":{"value":{"amount":"+0.8001875281333923","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1062912$7E02E8D6-6CC8-457E-879B-BF93C110240E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An analysis of a decomposition heuristic for the assignment problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_analysis_of_a_decomposition_heuristic_for_the_assignment_problem"}}}}}