{"entities":{"Q1417594":{"pageid":1428334,"ns":120,"title":"Item:Q1417594","lastrevid":48215527,"modified":"2026-01-03T23:53:40Z","type":"item","id":"Q1417594","labels":{"en":{"language":"en","value":"Randomized on-line scheduling on three processors."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2021245"}},"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":"Q1417594$758702E3-6752-4664-9704-6F5C00B584FE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"122260f21dfab6d7f76cb7538b68dc71745da496","datavalue":{"value":{"text":"Randomized on-line scheduling on three processors.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1417594$3765EF38-ACF2-45C4-8BBA-ABB2EF083B0F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"786004f1bb4aeb4f07dcd6d8f4dd271f6f60ba3a","datavalue":{"value":"1137.90524","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1417594$3A4CCBF2-EEC9-4E00-945E-10BFDF438010","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f9747a37b0b56aeca2085282046e2737cd5087ca","datavalue":{"value":{"entity-type":"item","numeric-id":96289,"id":"Q96289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1417594$5B4803C6-E450-4DB8-A3EA-BA5C55F3271C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"19dd558f6b0463011ea13c13314371f3bde474be","datavalue":{"value":{"time":"+2004-01-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1417594$B3F98B62-3294-49CD-A29D-EC4691AA696E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f3a900d55bbf67af237c614262b16760b4f28382","datavalue":{"value":"The problem of scheduling independent jobs on \\(m\\) identical parallel machines such that the makespan is minimized is considered. There was a conjecture that the lower bound  \\[  \\sigma_m=1+\\frac{1}{(m/(m-1))^m-1}  \\]  on the competitive ration for randomized on-line scheduling algorithms is the optimal competitive ratio for every \\(m\\geq 2\\). This conjecture holds for \\(m=2\\). An example is presented which shows that this conjecture is wrong for \\(m=3\\). Similar examples for \\(m\\geq 4\\) are still not known.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1417594$0E43D341-94A2-4B6C-9236-C5470BE9B0CF","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"647403b42bff8e5868a53244a891290fdc1b119f","datavalue":{"value":{"entity-type":"item","numeric-id":177705,"id":"Q177705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1417594$D665B7A0-2B5E-4CE4-9E5A-699E33F2FC33","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1417594$2D73D55C-04FF-4BEE-AAB3-2D1BBD041F33","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"73612f57bea3b7edd0c462bab216830ba2c6b723","datavalue":{"value":"2021245","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1417594$4B144775-881D-4657-B10D-821CAC0DDD8C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0605a1f2800486f9350885e9d3e822d311d76006","datavalue":{"value":"scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q1417594$8A8D88C4-8B76-464A-9ABE-7F0D0B900E83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f3dacb73fa9efa57cb94c5b919ad076d0f9817dd","datavalue":{"value":"parallel machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q1417594$DB58B2A3-00D8-4535-B7E6-4A75B3E944F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f2832e5ae4fc414c772c86f6023e26d563dd35e6","datavalue":{"value":"randomized algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1417594$3B2E028A-58A2-4BA6-8A4C-B2442632FF3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"56d85aa22959094ecc003ac28085d2ab6f8f44c0","datavalue":{"value":"competitive ratio","type":"string"},"datatype":"string"},"type":"statement","id":"Q1417594$56B57CBE-63F4-4199-8AE2-A002AAC016EE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b7707ad61e27825aebc34f5ef867f1a12b85c6cd","datavalue":{"value":{"entity-type":"item","numeric-id":250520,"id":"Q250520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1417594$7B59D29D-EDE3-4638-8622-AFF5F5F29285","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":"Q1417594$02FA4B86-80E0-4D7C-85E8-DFE91D6AAB56","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"881696af3a507a9f18f0aeb6f1b9b681447baf8b","datavalue":{"value":"https://doi.org/10.1016/j.orl.2003.05.003","type":"string"},"datatype":"url"},"type":"statement","id":"Q1417594$5AE642E6-2154-47F6-8E79-3061FB6CC7FB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ae2a3cee2eff6e04e4e226a0abdc1e86898f81f2","datavalue":{"value":"W2149452866","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1417594$D763DB39-7C15-4220-84AD-B287766B2F7B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f8695ab8067903991d76b877211314b9ae0d3706","datavalue":{"value":{"entity-type":"item","numeric-id":960514,"id":"Q960514"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1417594$074FDF08-66DD-4C03-B3E7-25FC8FF16A71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"392907b60e306d2faa3b5505f8451e97e9dbff07","datavalue":{"value":{"entity-type":"item","numeric-id":1336752,"id":"Q1336752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1417594$4CF4D7A2-1A84-4AEE-BEEE-1918921646F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b546d4be6791f7d4b96d8de0454eeaef69fe7a97","datavalue":{"value":{"entity-type":"item","numeric-id":1919176,"id":"Q1919176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1417594$6101AC68-AE62-465A-932E-02D357852802","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b0d4e47ba2dd4cad74d922241232407abb743aa","datavalue":{"value":{"entity-type":"item","numeric-id":1580957,"id":"Q1580957"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1417594$5AA2C3C7-DD2D-4FF5-84FB-C83A1D73812E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"97c41907ae7fce9a093033a958e4099f19fbdb46","datavalue":{"value":{"entity-type":"item","numeric-id":287130,"id":"Q287130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1417594$9A10CC50-192F-4976-A987-BF50E3D00B13","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fdb635b3134144c29578741cf55e7b3bf359a91e","datavalue":{"value":"10.1016/J.ORL.2003.05.003","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1417594$E3B41269-2950-4BFE-9767-53623382E5CC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8ca825168ac5ed9cf982193e7c6f5fbd0a3fbce9","datavalue":{"value":{"entity-type":"item","numeric-id":5096939,"id":"Q5096939"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"22bfb5a381eb9ee74c35d267eb45e178a781b33d","datavalue":{"value":{"amount":"+0.8679159283638","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":"Q1417594$97FDC242-D0B6-4548-B2D8-6ED77A300123","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a6834db8d2d3218efb72acd65a3c183dfb975e96","datavalue":{"value":{"entity-type":"item","numeric-id":2508042,"id":"Q2508042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cfc15ac5af0dfe0c77cd478e4d71a041b60436aa","datavalue":{"value":{"amount":"+0.8675404191017151","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":"Q1417594$DFCCE057-F3A0-4A01-8436-6F4003741160","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1a453abfbc518cd15749d7e9de6b753badaefecd","datavalue":{"value":{"entity-type":"item","numeric-id":1580957,"id":"Q1580957"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7dc6aa3c9d30bfbb2c9e0715b84ac2a9a1d53958","datavalue":{"value":{"amount":"+0.8664811849594116","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":"Q1417594$67EE65A0-920A-46CF-98CD-F989E896F4BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"70ea7ca467c4cbd872434eda185b481dfff972c1","datavalue":{"value":{"entity-type":"item","numeric-id":287130,"id":"Q287130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7dc6aa3c9d30bfbb2c9e0715b84ac2a9a1d53958","datavalue":{"value":{"amount":"+0.8664811849594116","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":"Q1417594$95449ED8-6436-4B3C-9951-8F9D00D7784C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c9ddc59853255574b18ee0af56c5314ae52eea5e","datavalue":{"value":{"entity-type":"item","numeric-id":960514,"id":"Q960514"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"101a4a845dde8461f4c7672cbd4930ca5fda9080","datavalue":{"value":{"amount":"+0.8651696443557739","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":"Q1417594$E21CF191-F614-4117-AEC3-E03027CF02D7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1417594","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1417594"}}}}}