{"entities":{"Q1058288":{"pageid":1060136,"ns":120,"title":"Item:Q1058288","lastrevid":67016403,"modified":"2026-04-12T14:21:20Z","type":"item","id":"Q1058288","labels":{"en":{"language":"en","value":"Dynamic storage allocation with limited compaction - complexity and some practical implications"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3900143"}},"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":"Q1058288$06DF53C5-272E-4C4C-BD29-72FCB488DB6C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e0de0a9f8b3ce5c17071ab1348a2452ed50b3e44","datavalue":{"value":{"text":"Dynamic storage allocation with limited compaction - complexity and some practical implications","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1058288$28F83DC8-5F43-4715-BE17-E0888869FACA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"aa3b2ce341f034a3113f1aebb27863101b4c9e6d","datavalue":{"value":"0564.68020","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1058288$3F0A39EA-66C4-43CA-A560-6D96207A8F9A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"667fc497eb3b375cd4bbe916b5e6d61c5ea3a055","datavalue":{"value":"10.1016/0166-218X(85)90046-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1058288$046A6A5F-5300-4EB0-9C2B-26B665DDBDE0","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058288$2AA7AE03-B8BA-488E-A022-E052B6AC5E7F","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":"Q1058288$EA00FCAF-70D2-4C81-B4F5-E0B5E5E13550","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a052ff601dd419de91e76fa6418b0887de6f3522","datavalue":{"value":"In the paper, the problem of dynamic memory allocation with limited compaction of contiguous segments, is considered. The particular question to be solved is to find, given the storage state, a free storage space of a given size by reallocating segments whose total size is minimal. The general case of this problem is proved to be NP-hard. It is, however, possible to give a linear time algorithm for solving a restricted case, involving only a few types of segment sizes. Moreover, for the general case several bounds on the storage size ensuring the possibility of finding in linear time a free space of the desired size by reallocating not more than L memory cells, are presented.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1058288$58A249D4-D46B-4086-84DB-F86CF0DD2A57","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"ec3769495799f08479987ac368adf64f125a2b66","datavalue":{"value":"68N25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1058288$1B4C839E-612F-4966-AACE-95CE7BD363CB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"31cae34882c92980b8d50a31a4e12022260fd6e9","datavalue":{"value":"3900143","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1058288$3F8939BF-9258-4838-9B53-27E03F43BF3D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2278f035590e400c7ab8ae4076c4d373dd8d0ebe","datavalue":{"value":"complexity of algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1058288$2CD46C6A-5DEE-4224-9DD4-D3AB495ED61E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc4837877785b4675d8ac1c6d4c911bcaf794e13","datavalue":{"value":"approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1058288$0CE0E7B8-D884-4536-83D2-7113E789F449","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bfc50e9ebbf57fc1351f53c09824ae122040d0b1","datavalue":{"value":"dynamic memory allocation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1058288$9460D692-97E0-4826-84AC-8F8A70511C09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cde4d2b8645f16d01c087c6df842cfea03eef121","datavalue":{"value":"contiguous segments","type":"string"},"datatype":"string"},"type":"statement","id":"Q1058288$E763AD8C-F1E8-4F53-8DE7-1961A4CB91FB","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"e054b167256846c8926b178c428b7185e1738b92","datavalue":{"value":"Q57387930","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1058288$C5E251C8-C36B-405B-9A07-5284C2DB7BFB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9ea65ac05d3711d20bfd41cd5b0225d93e7a7d58","datavalue":{"value":{"entity-type":"item","numeric-id":224835,"id":"Q224835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058288$4F5ABEEC-F80E-4EAF-AD80-EA5F10B77E1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ac4f09e64cb3be009d1d4b718b63a0b9c10a40ee","datavalue":{"value":{"entity-type":"item","numeric-id":293229,"id":"Q293229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058288$A9CCAB40-80E7-4ECF-B4B6-E7A6110E08EB","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":"Q1058288$CE1B0415-EFB0-4060-8A1E-7B203EB00842","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"508bc917a7771d26e78b44ecb3237422dc102dd5","datavalue":{"value":{"entity-type":"item","numeric-id":4066554,"id":"Q4066554"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058288$052F81F0-15E1-430D-BFF0-AC37C1D72112","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1be47688697e6c5eadc66e13eb0a02dc6451a458","datavalue":{"value":{"entity-type":"item","numeric-id":4142689,"id":"Q4142689"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058288$E1D0BA1D-9B43-498E-BA03-A5D688BE88D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058288$A5C7369B-FE91-486B-8C2F-17F3721EF983","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a58eb84f8246e3cfeb17afd7c957a3fe0040db82","datavalue":{"value":{"entity-type":"item","numeric-id":5528170,"id":"Q5528170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058288$9EECAD76-D94F-480E-AB5F-D3E76C563819","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dce9360a70dba425258e2ebbe390000c0976668c","datavalue":{"value":{"entity-type":"item","numeric-id":4194434,"id":"Q4194434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058288$523000D3-0485-49E2-BD1B-D6DF864923E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc6482fda869c7df0ed32fd6ade8f790a1ff04cc","datavalue":{"value":{"entity-type":"item","numeric-id":5585020,"id":"Q5585020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058288$CBA63153-D4E1-4E08-AFB7-F15E047D578B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c28633216ee5f9152578672ae664a4488e2c2cd4","datavalue":{"value":{"entity-type":"item","numeric-id":4162661,"id":"Q4162661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058288$999CED64-F993-4A1C-A399-00D281DC9ADD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d31ae1c68a7aa6b0aafa1aee37c5383bc7082120","datavalue":{"value":{"entity-type":"item","numeric-id":4070296,"id":"Q4070296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058288$ADA45290-58AC-4F0E-AF82-BE8EFF874EC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5da90de5703706367ae48655a5cbe97468fd26b3","datavalue":{"value":{"entity-type":"item","numeric-id":4066555,"id":"Q4066555"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058288$8CE5D9DD-79D0-46F1-972E-03D4B1F84BBF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e8006983bebae821d4dea107c3904e0d60b063d6","datavalue":{"value":"https://doi.org/10.1016/0166-218x(85)90046-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q1058288$1909D661-59DF-4E3C-A131-0EBA87F67F3E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"47c8e4904a2e722c09b68ed8f1b7627ba8606974","datavalue":{"value":"W2035105893","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1058288$1ADB20FC-217E-42BC-B00A-A6B56E987B6F","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"0c9d733534505f8ffe4e703ee3cd281baac266fc","datavalue":{"value":"journals/dam/BlazewiczN85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1058288$8905451D-C76E-4CBB-AB37-C1F25F9888EC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce11dddc700822c327eb92c6f08c3fe8cb4867b5","datavalue":{"value":{"entity-type":"item","numeric-id":3335008,"id":"Q3335008"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"864623717fbe105455629a3f00684a4a0d82ad00","datavalue":{"value":{"amount":"+0.8679164052009583","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":"Q1058288$1E8637C8-315A-4A57-A61F-E5B960EE6636","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5da163afd59fae3968391566467ba0507a80bedc","datavalue":{"value":{"entity-type":"item","numeric-id":3780409,"id":"Q3780409"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1ec2d6f773e4bbd942d89306e2c4992684d9dc43","datavalue":{"value":{"amount":"+0.817331075668335","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":"Q1058288$C5A16017-EEBA-4576-B233-056CD1E76E03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b45c06a882c3349a70be4a5640a11bded2c5f619","datavalue":{"value":{"entity-type":"item","numeric-id":4595477,"id":"Q4595477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1cefaedc8adc79b5f58d209ead7858534ab80f4f","datavalue":{"value":{"amount":"+0.8167994618415833","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":"Q1058288$095E9000-78D2-46B1-842A-5AF25054E026","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e0bceb4645fd08239d7002f8094bae880fd45ba","datavalue":{"value":{"entity-type":"item","numeric-id":3766837,"id":"Q3766837"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b5aed6bddcdfb4983218f633380181f11ebe6848","datavalue":{"value":{"amount":"+0.8089410066604614","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":"Q1058288$7607413D-96C6-442C-91DC-EDE6F6E55199","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7eadf55585219f3d081aef34fb316e02fe9e4309","datavalue":{"value":{"entity-type":"item","numeric-id":756873,"id":"Q756873"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bcae8218532ff0e64c17de65087e58158132c960","datavalue":{"value":{"amount":"+0.8000328540802002","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":"Q1058288$6B034862-D936-4409-9536-F6B11A9A7DD3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Dynamic storage allocation with limited compaction - complexity and some practical implications","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Dynamic_storage_allocation_with_limited_compaction_-_complexity_and_some_practical_implications"}}}}}