{"entities":{"Q1662587":{"pageid":1673328,"ns":120,"title":"Item:Q1662587","lastrevid":56787372,"modified":"2026-03-23T14:44:53Z","type":"item","id":"Q1662587","labels":{"en":{"language":"en","value":"Efficient algorithms for the maximum sum problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6920550"}},"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":"Q1662587$EFD7312C-8344-4A7C-9A6A-68F9313D57EA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"72eef952703b3fb820a544668ae0bc58490b9f08","datavalue":{"value":{"text":"Efficient algorithms for the maximum sum problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1662587$589F3125-57B1-4415-86EE-E87EBA44EBEE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"55af0c194ee85a1bd197a7ac96d3eb308c8cb8e5","datavalue":{"value":"1461.68250","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1662587$4D783963-9159-4087-922A-914C1313970E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"43031cf980c04cd7f0f3693d66fce3ed7141d520","datavalue":{"value":{"entity-type":"item","numeric-id":1662585,"id":"Q1662585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662587$0CC49B99-FCCA-4F0A-8A70-6DD51B82DBC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4183dc8fe578c15515685ddf7481cba0dc9b5e22","datavalue":{"value":{"entity-type":"item","numeric-id":1662586,"id":"Q1662586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662587$899ACAD9-A60C-46D5-A33C-7EEB12CF850E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fbd8d347166af77436aa4bae89e2c3259d9425c5","datavalue":{"value":{"entity-type":"item","numeric-id":350722,"id":"Q350722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662587$189E2F65-A724-4860-8CD9-EAED21EB8CCE","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":"Q1662587$3437420E-C348-40BC-87D1-B1082CF0E79B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"431a43c637c8a2264e4d8145aa5a3c26bfb96786","datavalue":{"value":{"time":"+2018-08-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1662587$1390FF5A-90BE-45E4-A629-5FA9DED3E93A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"845490c4efaf31aa29a2e2b5fe8f6223af39e65f","datavalue":{"value":"Summary: We present efficient sequential and parallel algorithms for the maximum sum (MS) problem, which is to maximize the sum of some shape in the data array. We deal with two MS problems; the maximum subarray (MSA) problem and the maximum convex sum (MCS) problem. In the MSA problem, we find a rectangular part within the given data array that maximizes the sum in it. The MCS problem is to find a convex shape rather than a rectangular shape that maximizes the sum. Thus, MCS is a generalization of MSA. For the MSA problem, \\(O(n)\\) time parallel algorithms are already known on an \\((n,n)\\) 2D array of processors. We improve the communication steps from \\(2n-1\\) to \\(n\\), which is optimal. For the MCS problem, we achieve the asymptotic time bound of \\(O(n)\\) on an \\((n,n)\\) 2D array of processors. We provide rigorous proofs for the correctness of our parallel algorithm based on Hoare logic and also provide some experimental results of our algorithm that are gathered from the Blue Gene/P super computer. Furthermore, we briefly describe how to compute the actual shape of the maximum convex sum.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1662587$112EEA9E-F6E6-41F2-ACD7-DA69E43BD24A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"79b3bc872b6637176b35f9e46ac855febbf884f5","datavalue":{"value":"68W05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1662587$761D48AE-347A-4BDD-835B-102ECAB79CB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8a784276b4e09d379c8147965411b455c3d79751","datavalue":{"value":"68T10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1662587$A974EC36-6743-435E-BCE0-E747F421F0DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de3565cfd3393000dd87ca545f95ff84d4c1446","datavalue":{"value":"68W10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1662587$BA49C21E-F621-4743-92EA-E9DF638159BB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"49b63d4e71a67c0e3efe14016d6fb345b0dafd84","datavalue":{"value":"6920550","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1662587$5D36CF00-AAC0-4708-841A-066E9E0CB125","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"72fc8d2e4ce91a8e1caff6e683de33ca63e493b1","datavalue":{"value":"maximum sub-array","type":"string"},"datatype":"string"},"type":"statement","id":"Q1662587$3F2C72A4-CFD3-420A-9CFD-84ED87C09176","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bd119361b5d52a88be138adb23a024067b778863","datavalue":{"value":"maximum convex sum","type":"string"},"datatype":"string"},"type":"statement","id":"Q1662587$32F0BD2D-462C-4CFF-9F51-922EF28C9A69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0967c5f93d36d6aa18ee008d77ee288965d952b9","datavalue":{"value":"parallel algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1662587$8E9B8A88-71AD-417C-9361-88F5EBB8FB17","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":"Q1662587$C53C54E8-8077-4FA5-B6EF-D1D50B7E1F2F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0505638a98f83611e6e160eeef4bf51dd299eb00","datavalue":{"value":"https://doi.org/10.3390/a10010005","type":"string"},"datatype":"url"},"type":"statement","id":"Q1662587$6A7C5259-1DBE-4FF2-9B1F-4EA4DC94A958","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"dd11bd241d444a4f81a256ad88647cf90f3594a0","datavalue":{"value":"W2570190023","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1662587$AFC05633-4D4F-4B72-B0FC-FAC5670DDAA9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"daf3c2db299ef624cd0e98c6166b7d5969c9294c","datavalue":{"value":{"entity-type":"item","numeric-id":3507285,"id":"Q3507285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662587$BE768ED9-6682-418C-87CF-425557A9518B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"899030754e56750b28c82d14ff3657c98d438691","datavalue":{"value":{"entity-type":"item","numeric-id":4250212,"id":"Q4250212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662587$2FADD215-E486-4EB2-8B09-367FEDDF53AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b9ee554a39b33f9f6d38109a26dd3ce52b5f94f3","datavalue":{"value":{"entity-type":"item","numeric-id":2841268,"id":"Q2841268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662587$9E9336E8-F870-4A75-9FE6-0BB3ECE51E89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"323dbd6fd6973b3663055cf97da83be885dd9ec7","datavalue":{"value":{"entity-type":"item","numeric-id":5569944,"id":"Q5569944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662587$A89EAFD6-959D-42C7-AE6C-E095AA146234","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4a9238fc49995a79f8c006683b1a9c42fafe2bd","datavalue":{"value":{"entity-type":"item","numeric-id":4085221,"id":"Q4085221"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662587$1C8395A2-A8F7-4785-B8F4-6342D06291D0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c266ca542ff0b4c0f3ca8f0ec7f1fee2a12eee7b","datavalue":{"value":"10.3390/A10010005","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1662587$C1127781-065D-447C-B473-E12FF11F989B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"be2a983765fab2262448b38ceb94279243d53db8","datavalue":{"value":{"entity-type":"item","numeric-id":2509030,"id":"Q2509030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e1c627b7b961b1db908c8a3ebca542946e72d8dd","datavalue":{"value":{"amount":"+0.9662699","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":"Q1662587$A7137B48-B0AE-4085-A705-E32C56A29DFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1cd8ef1d457d09491912547c3a87bf5cbc65a3f7","datavalue":{"value":{"entity-type":"item","numeric-id":5712105,"id":"Q5712105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e1c627b7b961b1db908c8a3ebca542946e72d8dd","datavalue":{"value":{"amount":"+0.9662699","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":"Q1662587$DA8A5A21-556D-4BB4-8683-312839C587A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"819315e8c4fd77e1b887fecee54abf19c473146e","datavalue":{"value":{"entity-type":"item","numeric-id":5459141,"id":"Q5459141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"37d94a93ec2d6e3750f3da94e98efe04fb8676f3","datavalue":{"value":{"amount":"+0.9465705","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":"Q1662587$DE4554FD-3501-427B-B229-088959D457A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"59d169423750869218fdeebcd617c973f4127ec0","datavalue":{"value":{"entity-type":"item","numeric-id":2268857,"id":"Q2268857"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"37d94a93ec2d6e3750f3da94e98efe04fb8676f3","datavalue":{"value":{"amount":"+0.9465705","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":"Q1662587$6EA3A7A2-4E70-4367-8052-7EB12AA6C19C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"322097b068ac4352837bf3bf64e04095c1b6d894","datavalue":{"value":{"entity-type":"item","numeric-id":2508973,"id":"Q2508973"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"01e1cddfed4efd56317333859181fae50aea1cc0","datavalue":{"value":{"amount":"+0.92739797","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":"Q1662587$8BE894A9-3FB1-441C-B742-F70A158437EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4c0d9059a8159755e7b322518d445a46f9aab4e1","datavalue":{"value":{"entity-type":"item","numeric-id":5897912,"id":"Q5897912"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"01e1cddfed4efd56317333859181fae50aea1cc0","datavalue":{"value":{"amount":"+0.92739797","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":"Q1662587$EC8BA3F9-3E7B-4DA2-9DC0-887CB0498EE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dd2aa3c58e8cf054224ac3720b433e3c43653bf2","datavalue":{"value":{"entity-type":"item","numeric-id":673936,"id":"Q673936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2be6b5638c8e3b75d6a44ae1e75b25ff8c065a5d","datavalue":{"value":{"amount":"+0.9235122","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":"Q1662587$94D70EF5-9A10-42F9-A3F9-7E9892D5740B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5e7aeaa22c4063798aa3904c0c4f90caec378df1","datavalue":{"value":{"entity-type":"item","numeric-id":3721818,"id":"Q3721818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4abbb08b0e3672a73740c8bb5f849449d0109fca","datavalue":{"value":{"amount":"+0.9057392","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":"Q1662587$2689D4D8-907A-4120-A95C-F221C3E5CE0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3f1ae51210b3dd5faa136a3024f912d1ccd13e48","datavalue":{"value":{"entity-type":"item","numeric-id":3525591,"id":"Q3525591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e5304f06fba43e4500b6ee1e587c2f6a347464e0","datavalue":{"value":{"amount":"+0.9042939","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":"Q1662587$78FC8133-FD4F-474E-86CD-2A26FA58D238","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a35f0e539364bdf3beb28c9e2ed8846b7ac3af2c","datavalue":{"value":{"entity-type":"item","numeric-id":4203809,"id":"Q4203809"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f1551b9adcb06a410a70d340bfcde926d0fff45","datavalue":{"value":{"amount":"+0.88054454","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":"Q1662587$D7386E40-FFC1-4A35-B2AA-D18A58804820","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":"Q1662587$4C893E34-A38F-4B8B-A385-B6C7ED51EC6D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1662587","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1662587"}}}}}