{"entities":{"Q1853182":{"pageid":1863924,"ns":120,"title":"Item:Q1853182","lastrevid":71501631,"modified":"2026-04-13T22:41:02Z","type":"item","id":"Q1853182","labels":{"en":{"language":"en","value":"On-line restricted assignment of temporary tasks with unknown durations."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1856510"}},"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":"Q1853182$20784665-27E6-4DBD-8481-3ACF12F54E02","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"18cf4508642518a311137647fe637e16d7df4880","datavalue":{"value":{"text":"On-line restricted assignment of temporary tasks with unknown durations.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1853182$73423452-EC3C-4F1E-A0DD-44902A6059EC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fdc5ef8d2d32a3d6cf2ef37f4b57b43522469e69","datavalue":{"value":"1042.68118","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853182$753B6350-DBD7-443F-916E-1843881572F3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0fb2fa657e1283c8610832ccbdd5e83410ef3c76","datavalue":{"value":"10.1016/S0020-0190(02)00350-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853182$49134ECD-E7EC-4A7D-94AF-69810168741F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"de6de96aecae3daaf3224a190274db6755543f1f","datavalue":{"value":{"entity-type":"item","numeric-id":627108,"id":"Q627108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853182$A87814FE-72FC-4143-8505-B491F23BAED0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"68814389157e3d8757e8eed17277cd2e82d90c5b","datavalue":{"value":{"entity-type":"item","numeric-id":526845,"id":"Q526845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853182$968D5372-BF0D-4EC6-9C2D-7865EB3C5F81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2c3269ab44f9669f0576537dce123fd34c697ef0","datavalue":{"value":{"entity-type":"item","numeric-id":189394,"id":"Q189394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853182$BE484E4B-25D6-42EC-AB43-4233462D2827","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d9f6b5d26f49366977cda1349aa1fe24902e4163","datavalue":{"value":{"entity-type":"item","numeric-id":375694,"id":"Q375694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853182$F661A6CE-E712-492F-8E96-CFBCD51E6F72","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853182$F54D39F2-B0A4-44EF-B89A-43C5DA2A2E6F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5b5e42af6f5e314fbfeffbcec47ae99c9eed44fd","datavalue":{"value":{"time":"+2003-01-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1853182$66B43080-F0FB-4EC6-9820-D0E1AEFAC483","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"20bc4873edc4fb2ba58848c4636c8073dbd87821","datavalue":{"value":"We consider load balancing of temporary tasks on \\(m\\) machines in the restricted assignment model. It is known that the best competitive ratio for this problem is \\(\\Theta(m)\\). This bound is not achieved by the greedy algorithm whose competitive ratio is known to be \\(\\Omega(m^{2/3})\\). We give an alternative analysis to the greedy algorithm which is better than the known analysis for relatively small values of \\(m.\\) We also show that for a small number of machines, namely \\(m<5,\\) the greedy algorithm is optimal.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853182$7739EE0A-3A73-4353-A550-F7AA30D7A00E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"79b3bc872b6637176b35f9e46ac855febbf884f5","datavalue":{"value":"68W05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853182$64BCFA11-553E-4681-967E-D99CDE04D261","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1c8f82ed29e9110c5487350ac2bb8792390d1735","datavalue":{"value":"1856510","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853182$1B80EE0A-C705-4123-A7F2-E10AFCD4097A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b7bcd354d3cafd63e238f661b84335318abe3297","datavalue":{"value":"On-line algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853182$62B47FD9-D58F-4DB4-8636-37F67148C563","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2b9e8b0f2ba8a2410e9446257cddfacfcf89d3a0","datavalue":{"value":"Competitiveness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853182$3299D7B2-B032-47BD-80C8-3F4E6D563D26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4cf8e6e447c31f57ab7b190b4a24abe9661cd112","datavalue":{"value":"Temporary tasks","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853182$BA5BDADE-D9F7-4942-842F-C73BAFFF1D04","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":"Q1853182$AB25ACB8-0C62-473D-ABE1-C870E388B44F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"268a51c8abca4fb9d22d700eb75559f07e6877f6","datavalue":{"value":{"entity-type":"item","numeric-id":4828923,"id":"Q4828923"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853182$BA234E3E-EF66-4A88-A11B-989D5ABD1C07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2593d62c5ee82f57d17a663342c5ab8f36b63416","datavalue":{"value":{"entity-type":"item","numeric-id":5248533,"id":"Q5248533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853182$C0C5262E-CD3D-4046-BF53-10EB58AAAAE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ea15f4327bcce3b12251b0956fe888a7877e7e8","datavalue":{"value":{"entity-type":"item","numeric-id":4230343,"id":"Q4230343"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853182$22EEC60D-ADE7-4D1A-8000-B278F7243537","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4016d254f0b0b7c443ad645f96363a4ccdd3bb4e","datavalue":{"value":{"entity-type":"item","numeric-id":3125220,"id":"Q3125220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853182$F02BA1C6-C147-4EA9-8467-FFF07009D80D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"058ccf53cb0e0e361fbb6a03a075cd9bc8192a06","datavalue":{"value":{"entity-type":"item","numeric-id":4763408,"id":"Q4763408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853182$A30F9663-FE5B-4364-B5AC-53C456124AA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df399851d600f5fc66b83855263f74637e3a379d","datavalue":{"value":{"entity-type":"item","numeric-id":5555416,"id":"Q5555416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853182$141403FA-C0A3-462E-A56B-E3B1E975C454","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6355846359bd20b4f90591c895cfca2d61119d49","datavalue":{"value":{"entity-type":"item","numeric-id":287100,"id":"Q287100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853182$8C9632FB-A5D6-4814-99FE-18669277A0BA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"98618690cb0ea0b65bd8effbdead0816dfae38fd","datavalue":{"value":{"entity-type":"item","numeric-id":5060106,"id":"Q5060106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d8bdfd5bb8b34f0e9a38b25d3ff8e781826c2d16","datavalue":{"value":{"amount":"+0.8894122242927551","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":"Q1853182$54F64067-1658-4A96-91F5-6A6A680824C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e79194a4f724b976b9640dd1c96d057bbd66a0d5","datavalue":{"value":{"entity-type":"item","numeric-id":3125220,"id":"Q3125220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e740e3683d73a2365125ed4bbcd98a68ef8e854f","datavalue":{"value":{"amount":"+0.8808911442756653","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":"Q1853182$85273B84-B41B-41D9-875A-2B543D5422B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d18178932e7fa047c13c943c085278abb14b52b9","datavalue":{"value":{"entity-type":"item","numeric-id":1853487,"id":"Q1853487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f76cb560018328953df67a72f26769438894d701","datavalue":{"value":{"amount":"+0.8808908462524414","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":"Q1853182$9B85A727-31BD-496B-87A2-5F91188023F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0e81c063a9a3a45816926e9e621e18f02da4987d","datavalue":{"value":{"entity-type":"item","numeric-id":2503355,"id":"Q2503355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e34a9e3a63d461df06ab4c6c35cf403e580c2050","datavalue":{"value":{"amount":"+0.8641165494918823","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":"Q1853182$A44BBE3A-2647-437D-83AA-AB10FA25469F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"af9d7f74f834e35672a46b741eba5d91ebbfdbf3","datavalue":{"value":{"entity-type":"item","numeric-id":1400898,"id":"Q1400898"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0f7d9edf216174baef0e4e99ed39c4b24bb7097e","datavalue":{"value":{"amount":"+0.8624407649040222","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":"Q1853182$1E471BE5-940E-4878-AD23-AD0A05A52D54","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On-line restricted assignment of temporary tasks with unknown durations.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On-line_restricted_assignment_of_temporary_tasks_with_unknown_durations."}}}}}