{"entities":{"Q1108928":{"pageid":1119677,"ns":120,"title":"Item:Q1108928","lastrevid":42882619,"modified":"2025-07-15T16:51:37Z","type":"item","id":"Q1108928","labels":{"en":{"language":"en","value":"A sequential dual simplex algorithm for the linear assignment problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4068608"}},"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":"Q1108928$E610BA88-34DD-4412-B698-26C3BDBB5EEE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a8a04d6062df5e742fe116683f7e9db7399309f2","datavalue":{"value":{"text":"A sequential dual simplex algorithm for the linear assignment problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1108928$833D3E41-2893-47F9-9F77-C33B203801C2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"87f60b9e01393d2b14a0fa65ab09f9a23913fc0f","datavalue":{"value":"0654.90053","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108928$59C6E7EF-DDA0-4746-AA20-6C94FA3B7C33","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"798ffbdc02891f11ead5f7bb390f80e91cedc900","datavalue":{"value":"10.1016/0167-6377(88)90082-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108928$F6E5213D-C78B-4B79-BAF4-92BA35E99A1C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8b72059c79faafd9930f2b00959c28e948e5a941","datavalue":{"value":{"entity-type":"item","numeric-id":686414,"id":"Q686414"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108928$86F57AA3-4AB6-4C92-ADFC-1F0B689FD74C","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":"Q1108928$B618D6DA-8227-4DA1-B1C0-89579E83AD1F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1108928$5E0BD150-ADBB-4C4B-B679-6C7D2B50FCC0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7ef418519c0a2dd607d8818f9009ce6af26b4a07","datavalue":{"value":"The linear assignment problem is viewed as an instance of the transshipment problem over a directed bipartite graph G. First the corresponding dual simplex method and its relationship to graphs is described in detail. This method starts with a dual feasible tree (paragraph 1). As a preliminary the already known ``strongly feasible trees'' and the ``dual strongly feasible trees'' for the assignment problem are introduced, certain properties are derived and the dual simplex algorithm of Balinski, which works in stages is described.    The main result consists of a new algorithm (paragraph 2) which also works with dual strongly feasible trees; but here a sequence of assignment problems over an increasing sequence of graphs each of which defines such a problem is solved. This algorithm gives the possibility to handle rectangular systems (i.e. for the set of vertices \\(N=U\\cup V\\) of G the sizes of U and V are different) in a natural manner, i.e. without any transformations which, for example, needs the Hungarian algorithm.    Finally (paragraph 3) it is shown that the developed algorithm works with \\(O(n^ 2)\\) pivots and \\(O(n^ 2\\log n+nm)\\) time complexity, i.e. the same complexity as other algorithms known in the literature.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108928$5739F13E-967D-4F14-B0A5-9F45AEF5DC19","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"63b70ec5cb69f5c5c9550409918141ca28bfae61","datavalue":{"value":"90C08","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108928$7194E51A-94F1-4FD4-8065-07839298BEDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108928$A894E225-1485-4DA4-9C85-D6A888781345","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108928$7251B3AD-1026-4FD8-B429-743BA3A617F1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6b2f3ea3be35d7da5b1555cc71f5a58eee2323d6","datavalue":{"value":"4068608","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108928$6EF1B3E3-076F-495F-8124-9D993943D82E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b511133f1d70986a0bdd6051d3bc39226432f8c3","datavalue":{"value":"linear assignment problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108928$BF6054F4-626E-44AF-92A3-62D6E8E9C210","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f75dfc6feb81fb48e0b0399127ddcf54a588e5e4","datavalue":{"value":"transshipment","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108928$22DD25B1-D91B-462F-A664-4C810D0509B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"531406f21bc08632ebe01e32152f47d30440f3b0","datavalue":{"value":"directed bipartite graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108928$B5129194-F30C-4C52-BC68-912E63D30E85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"34fa28a65d2b74b88503678977929053a39a12d9","datavalue":{"value":"dual simplex method","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108928$0EAB1650-D417-4064-BE30-8D1A2621C78D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f0aba471e544d295aaa8eb1111be578086c6817","datavalue":{"value":"dual strongly feasible trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108928$D26765AC-683B-46F8-B4B2-E73E2BFB66D1","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"31cef456e8646accdc28b523a232a52220366047","datavalue":{"value":{"entity-type":"item","numeric-id":593309,"id":"Q593309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108928$D1DBA45E-A600-430D-8931-B207E30C0D4E","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":"Q1108928$0170E58F-C62E-4149-925C-6AA7C2FB11F9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d362cdbae8753ae6145c8b5a0418343facb9792","datavalue":{"value":{"entity-type":"item","numeric-id":3706837,"id":"Q3706837"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108928$31804B5A-32C3-4474-AF83-EC701AE1AC9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5cc557944a61ff836b015040d814d55497ac85b2","datavalue":{"value":{"entity-type":"item","numeric-id":3730345,"id":"Q3730345"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108928$C4377C78-31AC-49B3-8850-789271AEBD2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55b8d1f1dec187949c55d24425e38fee6023c1bf","datavalue":{"value":{"entity-type":"item","numeric-id":4159200,"id":"Q4159200"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108928$72FECE2C-2C9E-4AD9-9A0E-E57D21F980E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe7c4b3192fc9d49664f31462adad1c716877534","datavalue":{"value":{"entity-type":"item","numeric-id":4123079,"id":"Q4123079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108928$927DAF80-F455-4207-9EC8-632824F06275","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6704ccbb4c75ac5e07412c0181b63f464f1b7a0e","datavalue":{"value":{"entity-type":"item","numeric-id":5225293,"id":"Q5225293"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108928$6279E3C1-4E7C-41DE-8C16-7EED2174B07B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"71d71bba0a80ecfea05317bc3e22648cd703b297","datavalue":{"value":{"entity-type":"item","numeric-id":3701192,"id":"Q3701192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108928$EEFED24C-E97B-4122-BBEC-13C7A6FDF452","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc6e689ca9104617943bd76b284824e0c9ceb6bd","datavalue":{"value":{"entity-type":"item","numeric-id":3707420,"id":"Q3707420"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108928$2F3E02A9-9BA7-40A8-BFEB-7036F4BBB4DC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bbb3bb949009cf68279203705ad8d01b9cedb77b","datavalue":{"value":{"entity-type":"item","numeric-id":3701192,"id":"Q3701192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6b3cc295a81e46fa52f291d3027ab70fd1879533","datavalue":{"value":{"amount":"+0.9215076","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":"Q1108928$325DF8BF-C294-44E5-916B-BF8768AB23BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"10ecea22cfffacfee94b29f1aad27685cbe7160d","datavalue":{"value":{"entity-type":"item","numeric-id":761971,"id":"Q761971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5c642e0a5c4ce0356e6d368bbe1e603b915daf6b","datavalue":{"value":{"amount":"+0.91592824","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":"Q1108928$4D435D48-463B-441C-98DE-AAE601CEA8DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4f9ecb3b49c5a6779426cbfc5f185c910e4d62b6","datavalue":{"value":{"entity-type":"item","numeric-id":3730345,"id":"Q3730345"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a1ab291693ce3571a5a19e1a0dac23276e3e5f3","datavalue":{"value":{"amount":"+0.913802","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":"Q1108928$DF8370F6-185D-440F-8C0A-E2048D55F870","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"acdb8427504044aff4fb79027f86fa19dc93605b","datavalue":{"value":{"entity-type":"item","numeric-id":1365112,"id":"Q1365112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5fa3889ef7cd8b26162c0136c007dbca8b5b141c","datavalue":{"value":{"amount":"+0.9104364","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":"Q1108928$2BADA9A1-3BC9-441A-BC9E-0A32025ACD37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4385caaa88ab0fe6142968b440bc7435b467408e","datavalue":{"value":{"entity-type":"item","numeric-id":4717146,"id":"Q4717146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"71080dd0289d3e787c024404539c81ed5a91c521","datavalue":{"value":{"amount":"+0.90625674","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":"Q1108928$2F8EF1AB-0FE3-411E-BD18-4AC251DB489F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6147ba39313b6cdd16cd1b4d8c07c7531db76796","datavalue":{"value":{"entity-type":"item","numeric-id":4006619,"id":"Q4006619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7869de4eab6b19ba6e000709f1b5ed2a83a2d4a5","datavalue":{"value":{"amount":"+0.9016675","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":"Q1108928$39CBCC72-DABA-467C-9B4A-6D2B7E7B6B1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b7e266ad5437bdb243316a8b94d00442902c3534","datavalue":{"value":{"entity-type":"item","numeric-id":4006909,"id":"Q4006909"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"53b19dc211773ed5e10df7db71df7d8fef8ab0fd","datavalue":{"value":{"amount":"+0.8975529","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":"Q1108928$5F33689F-2AA9-4E79-B362-41BF2D0E8208","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8473333698e2178bdfd5122aacabd0f354eb9360","datavalue":{"value":{"entity-type":"item","numeric-id":3696867,"id":"Q3696867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a8c30f612aa2f8e28c3e9370e60dc1587032042a","datavalue":{"value":{"amount":"+0.8970741","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":"Q1108928$E83E638F-EDF9-49CB-89DD-4F608BB2F80A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78f0bad9f6df1db3e69aef90c933d05f893a3812","datavalue":{"value":{"entity-type":"item","numeric-id":581226,"id":"Q581226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd12d15036693a80b8f7392316cb64556d6e1443","datavalue":{"value":{"amount":"+0.8966663","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":"Q1108928$204D622B-909A-466B-ABFC-AFFC3A87D42B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"86da101da47d2d513482ede8eddbf4984da25acd","datavalue":{"value":{"entity-type":"item","numeric-id":4283454,"id":"Q4283454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"93cbf90a51ef75e0d5842d1c12f43f2c7279f200","datavalue":{"value":{"amount":"+0.8877245","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":"Q1108928$1FC1AAAF-7BCA-4B88-9362-A8F684BE049E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1108928","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1108928"}}}}}