{"entities":{"Q1116656":{"pageid":1127405,"ns":120,"title":"Item:Q1116656","lastrevid":69680535,"modified":"2026-04-13T08:40:16Z","type":"item","id":"Q1116656","labels":{"en":{"language":"en","value":"An algorithm for the detection and construction of Monge sequences"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4090700"}},"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":"Q1116656$4943696C-4E9F-4187-BA72-65D543D4DB51","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5fa3ba4ce949b6f7fdf45dc7a56c645348669b37","datavalue":{"value":{"text":"An algorithm for the detection and construction of Monge sequences","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1116656$6BF349F8-6BC5-4C0A-A07F-03913FF66741","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e125ce59c349e39fd700d88837b40d24a18fd595","datavalue":{"value":"0666.65044","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116656$82862ECC-4085-46C1-B105-B4E1C0DFEFC2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"19c69f82134fb20ed975ddda2a5090deb73a4ab7","datavalue":{"value":"10.1016/0024-3795(89)90487-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116656$D725D963-0093-4A37-9908-48C5B564B297","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"aa74685ea3a43e46bd3b733b87a540219cb373a3","datavalue":{"value":{"entity-type":"item","numeric-id":1116655,"id":"Q1116655"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116656$2DE79BEB-9B66-4D32-A147-F938C1D51764","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5b969806e15667b8bb837290cff38032bdae579d","datavalue":{"value":{"entity-type":"item","numeric-id":242829,"id":"Q242829"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116656$1F1FCB9F-EA2F-451F-B574-CF60F6E69A5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c86f85759000edd4a75c5506bbb76118e6ada90c","datavalue":{"value":{"entity-type":"item","numeric-id":214970,"id":"Q214970"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116656$D7CA2B7F-82E7-4222-AAE1-15D8FF0156F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c61d0b4df374523ec5b59f8a7d6c81266878fe30","datavalue":{"value":{"entity-type":"item","numeric-id":178698,"id":"Q178698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116656$5781804F-4DB6-4DA2-B42B-39EE1589F7B0","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"8de031de05325b44570d0c47c3ec8813873d565c","datavalue":{"value":{"entity-type":"item","numeric-id":92813,"id":"Q92813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116656$80F4F6BA-EEA1-4BC5-8FA6-D909BD0AF0EC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-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":"Q1116656$1881B21F-CDD7-4F69-8F33-D98658E4FD4E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ec48516cd63c8ae7f468713fe0a9131c7be0d020","datavalue":{"value":"\\textit{A. J. Hoffman} [Proc. Symp. Pure Math. 7, 317-327 (1963; Zbl 0171.178)] proved that a transportation problem can be solved by a greedy algorithm if there exists a sequence (called Monge sequence) of pairs of indices of the cost matrix \\(C=(c_{ij})\\) such that if (i,j) preceeds both (i,s) and (r,j), then \\(c_{ij}+c_{rs}\\leq c_{is}+c_{rj}.\\) The authors describe a general algorithm which generates a Monge sequence whenever it exists and prove that for an \\(m\\times n\\) matrix \\({\\mathcal C}\\) it requires \\(O(\\bar m^ 2\\bar n \\log \\bar n)\\) time and \\(O(\\bar m^ 2\\bar n)\\) space where \\(\\bar m=\\min (m,n)\\) and \\(\\bar n=\\max (m,n).\\)","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116656$FFECDB49-7409-4CF1-AE44-046BADC2ACE5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116656$6FBA0A52-2A3C-4507-A9B9-C8E365E0C0D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"63b70ec5cb69f5c5c9550409918141ca28bfae61","datavalue":{"value":"90C08","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116656$D4A0051A-23A9-43E4-94B7-69CD57578AA9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"fd1f75592e151cf5b3672865e416efc829c9ab75","datavalue":{"value":"4090700","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116656$A9082A20-00C0-4668-8C59-BDEEB6A150A6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"248b10e56fbedd9274c469d28ff709164505189b","datavalue":{"value":"transportation problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116656$EC8B1517-E2D6-4000-B885-45CF89932109","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e1e7eb452ae4c92c43fa47bb0afb8177365a429","datavalue":{"value":"greedy algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116656$435797F2-5398-4EB4-9B8E-80D9E0D1423E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"31653e810792d99f2bf930fbf40bae624716891e","datavalue":{"value":"Monge sequence","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116656$6394CA01-0BCB-4C89-BC82-9D8F797963C0","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"a6ba53c58e0084a9f17d607fb0ad639f8cc8b0b7","datavalue":{"value":{"entity-type":"item","numeric-id":277136,"id":"Q277136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116656$8D32ECCC-D9B4-4D4E-A886-CF56D432DA68","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":"Q1116656$9011932E-8FE4-4FFA-8B16-58222D08C897","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"66e373367593baccdffcd4bad3ab9b020a7d88c7","datavalue":{"value":"https://doi.org/10.1016/0024-3795(89)90487-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1116656$DEBB735E-664E-4740-A144-8ADC5452D33E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"60b560f7d9b5d9f05730c1da33ba5ff12113f614","datavalue":{"value":"W2045879812","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116656$3B5D2DEF-2C19-4ECC-8B93-4ADEC84204BE","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f75ccbc4715043ffbe1524dd237b6818c7b5d214","datavalue":{"value":{"entity-type":"item","numeric-id":3718481,"id":"Q3718481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116656$AC11C013-1CCA-44BA-BB32-C3924E329A2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a561a2f04b24d2a62f33ee92c88831d127f55e0d","datavalue":{"value":{"entity-type":"item","numeric-id":1080781,"id":"Q1080781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116656$4CFDCB0A-7ADD-4931-B4F1-FF96274E08E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a43ca27cba6b8cbde68d00987a946f9cde333444","datavalue":{"value":{"entity-type":"item","numeric-id":3844775,"id":"Q3844775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116656$DD300305-A565-4C8C-B727-CAA2EB1DAA42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a10d9726bd833217e3e0ca3cedd2d986dbf6d0d6","datavalue":{"value":{"entity-type":"item","numeric-id":5331678,"id":"Q5331678"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116656$8C4B8EDE-E35D-4ADB-BE51-BD8CAB69C713","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d2c893b7b17db5da0cf71bed489830282949b84","datavalue":{"value":{"entity-type":"item","numeric-id":3768703,"id":"Q3768703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116656$A831075B-129C-497D-9A9F-58A4D2FC9BC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2260b996422f953b9b92d577d1bb801544dd765","datavalue":{"value":{"entity-type":"item","numeric-id":3285991,"id":"Q3285991"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116656$2E0F4E08-9745-4ED8-B9A5-CAEE5BCE2D08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"616ca60f929dd1155b60b5f9fc6d66744d501fc8","datavalue":{"value":{"entity-type":"item","numeric-id":3980518,"id":"Q3980518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116656$07F2DC22-6232-4ABE-93E3-61DA6C3E7DCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"86b64e2df3bce48bd31882b43072b00c8eefc0e7","datavalue":{"value":{"entity-type":"item","numeric-id":5838558,"id":"Q5838558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116656$86E2C948-3607-45B5-A931-4EF1E43F8BE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"242f6732c9aecb9180d76230dd0b3ce80be5a4cb","datavalue":{"value":{"entity-type":"item","numeric-id":4130999,"id":"Q4130999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116656$BE8A3234-49BE-495B-9BC3-AB9A60A44F20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5623e7f634c4dc6c5719711df6c0f6e5ab6354c","datavalue":{"value":{"entity-type":"item","numeric-id":5648142,"id":"Q5648142"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116656$49676A98-368A-4968-A4DE-3BA94E9B27E7","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":"Q1116656$57584708-0F19-4606-AA8B-212A76A2E814","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b553cfb85bf45e1596d5266c3fc7d2fdecba1b57","datavalue":{"value":{"entity-type":"item","numeric-id":1375084,"id":"Q1375084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"83b307131d188b3646a2d14cccc960fc64df7530","datavalue":{"value":{"amount":"+0.8986427187919617","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":"Q1116656$4E91EB2A-4F4A-46F8-89EF-E56B880D9A85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b4ba678397eea9048ca3dd2687465af168fdaa95","datavalue":{"value":{"entity-type":"item","numeric-id":685703,"id":"Q685703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"09185cae639448a27b323089c9d2337654188cb1","datavalue":{"value":{"amount":"+0.8889322280883789","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":"Q1116656$8134B7DD-8D22-48B3-8656-3D4160E7DA8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bee12374b55b3d7ab2737c43e3204f0ea9cc90d0","datavalue":{"value":{"entity-type":"item","numeric-id":1805449,"id":"Q1805449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8bb1ffb786db7a8c398653c9aa398a3e77d85e6e","datavalue":{"value":{"amount":"+0.861969530582428","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":"Q1116656$EF5CEF2D-C1A7-4DA7-AA35-27A6ED1F2924","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f4ad2632cd936dad8c99493b0852dace5844b334","datavalue":{"value":{"entity-type":"item","numeric-id":2450613,"id":"Q2450613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2af4cc76eab83454cb0a2dd2f0e53a121db12699","datavalue":{"value":{"amount":"+0.8583236932754517","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":"Q1116656$2DD9AA37-6997-4A3B-9657-07A7CFDF9A1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"16da3d7d9946ba32c17be99ff423df4edd40b56b","datavalue":{"value":{"entity-type":"item","numeric-id":686244,"id":"Q686244"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"26678acdb4a920b58752a0f85b08a2260440ba8b","datavalue":{"value":{"amount":"+0.854516863822937","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":"Q1116656$D7F5A4EE-8A91-4869-87A9-040BB9084770","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An algorithm for the detection and construction of Monge sequences","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_algorithm_for_the_detection_and_construction_of_Monge_sequences"}}}}}