{"entities":{"Q5946816":{"pageid":8123618,"ns":120,"title":"Item:Q5946816","lastrevid":97694759,"modified":"2026-06-05T15:14:44Z","type":"item","id":"Q5946816","labels":{"en":{"language":"en","value":"An approximation result for a periodic allocation problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1660373"}},"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":"Q5946816$4882E2E7-DC7D-4839-9954-40A307813FEC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"bc890f201e3776c27df5ad5f40e3d0be052bdb83","datavalue":{"value":{"text":"An approximation result for a periodic allocation problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5946816$A0444318-9EA6-47D4-8E74-392534050459","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3eb2c73e28b04f4134e465a5e146c1ae21778825","datavalue":{"value":"0994.90065","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5946816$7A7FD0AA-3E1E-445B-A175-85280EBE6A46","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0eb12971617fffea7db0ae7ace157ad96a9438a0","datavalue":{"value":"10.1016/S0166-218X(00)00309-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5946816$B3B83679-304A-4C57-BDB5-F2ACE965FBEF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c054a6baf09581e119430a0f0cf8ef64bdcf858f","datavalue":{"value":{"entity-type":"item","numeric-id":210505,"id":"Q210505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946816$C7C2D3D8-ABBF-4487-82C4-14F1052006FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"05f8aaa1fcaa350ea29e602aa878272ced422c6b","datavalue":{"value":{"entity-type":"item","numeric-id":190513,"id":"Q190513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946816$68BF3439-A928-4C64-9542-CFECBC4B61C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7313d1fd8b1d21fd358d6a5a11163b1ac4428177","datavalue":{"value":{"entity-type":"item","numeric-id":210506,"id":"Q210506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946816$5F176A3F-80DF-40E6-8EAB-939FF3422FA2","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":"Q5946816$00CE7729-A683-4465-BB30-3F96BD0AC985","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"231746dd1b162532443840a32e2f1ac3f5dc4bf7","datavalue":{"value":{"time":"+2002-07-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5946816$85A95857-751C-4E2D-A3B1-20E32C464FA4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"330247301ef49c3710a7ec8d0cc68f151b69d036","datavalue":{"value":"The paper introduces a periodic allocation problem which is a generalization of the dynamic storage allocation problem [see, e.g., \\textit{E. G. Coffman}, SIAM Rev. 25, 311-325 (1983; Zbl 0521.68027)] to the case in which the arrival and departure time of each item is periodically repeated. This NP-hard problem can be regarded as an interval coloring problem on weighted circular arc graphs. The main result says that there exists an acyclic orientation of a Helly proper circular arc graph \\(G\\) in which each path of the orientation is contained in at most two maximal cliques of \\(G\\). This gives a 2-approximation algorithm for a class of periodic allocation problems.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5946816$50978194-F0F1-4F9B-8041-F775DC89E44F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"28b1fb367b3a6335e647ddbd540f63d134723dd1","datavalue":{"value":{"entity-type":"item","numeric-id":222481,"id":"Q222481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946816$DDB136D5-471D-497C-BF3E-84930EA65784","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5946816$A87B56AE-DD32-4151-9B05-A0CEFCF80F01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5946816$A9065287-AADA-4108-A864-460062949490","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5946816$B4A921C7-5944-4FD6-BF4C-9DB121D11AC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"239a4a174af03c82b61364f762873d53ef0a37ef","datavalue":{"value":"05C90","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5946816$1B1F96C3-9E09-4936-ACD2-DCAA03B576AA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d7e35bdd393e8b652d7d8719b99dc188276e5740","datavalue":{"value":"1660373","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5946816$B99D9167-D51E-4F57-81EA-17C66FADC66E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ddc14051a93e8c78a1da682d6f4184d91e9c6088","datavalue":{"value":"graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q5946816$9AF177DD-ED35-4C7B-94EB-E49D5DD2F287","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b700c6a288eac9e459d4921ad6a78d11ad4ceac2","datavalue":{"value":"periodic allocation","type":"string"},"datatype":"string"},"type":"statement","id":"Q5946816$CFCE4FD4-4326-4560-9EEC-AA7EEB33560C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cba7479de0ebacbeccc7cd1db49a5e981a25660f","datavalue":{"value":"multiprocessor task scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q5946816$A8197577-BEA6-48C1-96B6-2FA366087017","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"788ec43786d127bf62e1bbf0b473c43a7c87ad23","datavalue":{"value":"interval coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q5946816$ECDF1672-56C8-4B56-B7A8-1E8D8AEB6A6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4e1780000149a6841fc7293614b6f16c5ba3a690","datavalue":{"value":"circular arc graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q5946816$098C572E-2CFD-444C-BEB2-E3A3DDC7D06C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d05f6036e6fa6ac0e370528ac36af787bba46d8e","datavalue":{"value":"clique partition","type":"string"},"datatype":"string"},"type":"statement","id":"Q5946816$489F8AB0-47BE-4AD3-9C7E-71F971E09DDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"af787d1b4b14af1c021acee5efc3a18774584b59","datavalue":{"value":"Helly property","type":"string"},"datatype":"string"},"type":"statement","id":"Q5946816$746AF9A2-1671-473B-A35D-6E1735394BB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0de600cf8191fa1f423fd01c9a02b172072a7391","datavalue":{"value":"approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q5946816$D5EBEDD7-E0FE-463A-A7D7-86FA53CBFCF6","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":"Q5946816$AF9156A2-F161-45BC-8323-DCE3267CB966","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"75f71ca3d542a1cea4c80a2aaf756f992939aa9d","datavalue":{"value":{"entity-type":"item","numeric-id":1322203,"id":"Q1322203"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946816$B8B16A57-F99C-4B5C-8EB0-1D637D8CAFBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a697534e400c292fd7900c800f84e9590cbffbc","datavalue":{"value":{"entity-type":"item","numeric-id":3670545,"id":"Q3670545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946816$03D06490-3F66-49C9-AA8C-463B40888B17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"42e3f64808792df3f3acce9b2d26acfea54debc9","datavalue":{"value":{"entity-type":"item","numeric-id":4250862,"id":"Q4250862"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946816$5770786A-E6EA-44D8-9643-8D87F4654214","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0708dc922a9ea94334bf71862f0083874aaeeb1d","datavalue":{"value":{"entity-type":"item","numeric-id":286992,"id":"Q286992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946816$92691310-75FC-4F17-BCCB-7D0C1418FA36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f8f32c0f8d3a8d987fa5117190e3642ecd32def8","datavalue":{"value":{"entity-type":"item","numeric-id":5961606,"id":"Q5961606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946816$FF9837AB-8AAC-4B9B-BB6A-D662CD1BBF6B","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":"Q5946816$C24D848B-4D42-40E4-8A5A-6548DFAC2F08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8966655ecbb1863d7d15b1de7a7a366acdd2bc41","datavalue":{"value":{"entity-type":"item","numeric-id":3964622,"id":"Q3964622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946816$6143AC44-9444-4A96-9E04-86CEFF2EFF5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f171b45557bd6ba2c91d5444caf4ff5931e9df1b","datavalue":{"value":{"entity-type":"item","numeric-id":4067141,"id":"Q4067141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946816$7C089063-CB9A-4750-BBDF-B071E3122F8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"79951ef0e863b253085b18ac522b96a0e34f5b4f","datavalue":{"value":{"entity-type":"item","numeric-id":4595477,"id":"Q4595477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946816$582E26E1-743C-4D2F-92EB-275C3BCC4673","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c17b1143dff0bc685088f8d62dbc046a1f96e02e","datavalue":{"value":{"entity-type":"item","numeric-id":5732670,"id":"Q5732670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946816$08A4BFB7-5B40-4EF2-A0D5-02536504A641","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49716778d2052bc48c41f915a376cfa1f999ef74","datavalue":{"value":{"entity-type":"item","numeric-id":3328583,"id":"Q3328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946816$D5B5121F-6BB8-45D8-AD63-24E93DA8DDB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53adffcde85757731399caa2865fb984ffe87a55","datavalue":{"value":{"entity-type":"item","numeric-id":3815536,"id":"Q3815536"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946816$B6972804-735B-42D9-8D96-F4A841BB5AC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a3fa9e9f0be77cb85cbf4adb4dd8bcc8a268a92","datavalue":{"value":{"entity-type":"item","numeric-id":1176726,"id":"Q1176726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946816$826321CB-6EB4-4918-B415-6CB8CE62B615","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cfd444ac2099fb3b5a15da02a0171b8b4a45b7ea","datavalue":{"value":{"entity-type":"item","numeric-id":5588432,"id":"Q5588432"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946816$61024CC2-A795-4CB1-97E0-2DDB0C08AA46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"748916b0bd02314d267ee1fd63d0d643e49c30f6","datavalue":{"value":{"entity-type":"item","numeric-id":2533745,"id":"Q2533745"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946816$782A16F7-00F8-431F-9996-8271FBD1904B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b7eadd6302524fe0279369bf2a3e30a02dc9c4f2","datavalue":{"value":{"entity-type":"item","numeric-id":2563173,"id":"Q2563173"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946816$020394DE-6444-4688-A68D-167EBA3E59DD","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"1a40a18b5b81693add0aa2570d9982ee85f45d18","datavalue":{"value":"Q126975307","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5946816$4D052CF9-0C18-44D2-B277-847EF47915E6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b79c82380d4d933d9aa879f88ada6f4fd40ebf08","datavalue":{"value":"https://doi.org/10.1016/s0166-218x(00)00309-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q5946816$84B37E17-6861-4343-8C4F-D75D5FD896DB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9a2e41521badc1199fdad38fb79b480b546d676a","datavalue":{"value":"W1991815181","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5946816$A3877A98-FA23-48E3-A2EC-991D4DACFB6A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2911a4691da0f0f3c60629f3ea44a563f5bdb5a4","datavalue":{"value":{"entity-type":"item","numeric-id":1176726,"id":"Q1176726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cfb30c7040688b8cd3035e97cb6cd1eaa869f3c3","datavalue":{"value":{"amount":"+0.8130051493644714","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":"Q5946816$6584421B-3AF7-408B-A05F-C3C4095597DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"256e87cfb9b7156e4d4fb86dc44c88fd7fb069e0","datavalue":{"value":{"entity-type":"item","numeric-id":1329789,"id":"Q1329789"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a742c8da416982bd65c17cb9a92cbee65092f6d2","datavalue":{"value":{"amount":"+0.8068543672561646","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":"Q5946816$42836BD4-7FD1-4B1A-A064-EA400BE4A9B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b7e78e935e869d678c01593c32afc0100a4c6136","datavalue":{"value":{"entity-type":"item","numeric-id":5945920,"id":"Q5945920"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a742c8da416982bd65c17cb9a92cbee65092f6d2","datavalue":{"value":{"amount":"+0.8068543672561646","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":"Q5946816$F73142B1-F6AC-430D-8CB7-1D4E575EA0DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d18d90f5da5f9cf339bb00d2620b23a37d6742ac","datavalue":{"value":{"entity-type":"item","numeric-id":1768168,"id":"Q1768168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1fa4ec05c0aa6daa8cf7103b29d2d4987601564f","datavalue":{"value":{"amount":"+0.7688034176826477","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":"Q5946816$33D84A56-62CE-4778-B46A-B1E4C160C77E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ab3451435660c925cf06ab5e69f3318cd43040cf","datavalue":{"value":{"entity-type":"item","numeric-id":2569164,"id":"Q2569164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1be64bebb007b6670443e37f01dffd63b7befbd4","datavalue":{"value":{"amount":"+0.7685437202453613","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":"Q5946816$0061EE1F-6048-4B60-A06E-599F776DB056","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An approximation result for a periodic allocation problem","badges":[]}}}}}