{"entities":{"Q507314":{"pageid":509081,"ns":120,"title":"Item:Q507314","lastrevid":62399319,"modified":"2026-04-11T05:49:13Z","type":"item","id":"Q507314","labels":{"en":{"language":"en","value":"Approximability of average completion time scheduling on unrelated machines"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6680628"}},"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":"Q507314$0DDF0925-0E7C-4801-A357-4D7ABB97DBEF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"05101d93d9c9b8fd2d7a4811ec55d76cd5185e3c","datavalue":{"value":{"text":"Approximability of average completion time scheduling on unrelated machines","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q507314$7F8D0400-0B8A-4450-B256-8D7C0D98D38E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ee12b710861a7b5e924cf6283779a33afe90bf1b","datavalue":{"value":"1357.90059","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q507314$5F4385BC-F93F-4CF0-BFD1-38B8628447CA","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"99da72655942e9c2c9c01874c026b7cceeb02de6","datavalue":{"value":{"entity-type":"item","numeric-id":163006,"id":"Q163006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507314$19AACD49-579B-433A-906E-B4E626ECE741","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f077fc2ce013ec6748bf1bf77b2e03417e1ed3a4","datavalue":{"value":{"time":"+2017-02-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q507314$4FC38216-A366-4515-80AB-F58F30DBC72A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"88d9d9051157b4caa9fa727d1dc760b9d9e10b48","datavalue":{"value":"This paper deals with the unweighted and weighted versions of the problem to minimize total completion time on unrelated parallel machines if preemption of operations is allowed. In Section 2, the author proves that already the unweighted version of this problem is \\(\\mathcal{APX}\\)-hard.  The second contribution of this paper are two approximation algorithms for the weighted version of this problem in Section 3. The first approximation algorithm is based on the 2-approximation algorithm given by \\textit{M. Skutella} [J. ACM 48, No. 2, 206--242 (2001; Zbl 1323.90024)] and has an approximation ratio less than 1.81. The second algorithm is obtained by applying the first algorithm and another algorithm given by \\textit{M. Queyranne} and \\textit{M. Sviridenko} [J. Sched. 5, No. 4, 287--305 (2002; Zbl 1009.90046)] and taking then the better of the two solutions determined. This latter algorithm has an approximation ratio less than 1.698.  The results of this paper fill a gap in the complexity classification results for this objective function, and it also improves the previously best known approximation ratio for this problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q507314$3C5006CB-560A-4FD1-B85F-4491B2A38C5A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f9f554eb64639799bf090dd0dfa97bafd06e8c2c","datavalue":{"value":{"entity-type":"item","numeric-id":229433,"id":"Q229433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507314$D5A13E86-8077-4BF9-A3A7-542377DCE70B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q507314$F42DE938-4BCC-45FB-A066-8F13D2C1A83B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q507314$1FDD5906-A88A-4A34-B763-48B48602B38E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q507314$B80A3294-9D3F-4700-ADD2-F547BB370765","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d7685fcf9c0241b77890f3921e0c683b5c3a6938","datavalue":{"value":"6680628","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q507314$89D8688E-2F93-490A-9775-819EDDAECC13","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0605a1f2800486f9350885e9d3e822d311d76006","datavalue":{"value":"scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q507314$ED143B43-2523-46AA-9471-30BA9DEB2B4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f5f52b22d40422b56ec68a7c55092408445459fb","datavalue":{"value":"total completion time","type":"string"},"datatype":"string"},"type":"statement","id":"Q507314$40BFEA02-CCAF-440C-AC57-253A8419DCB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"093b6cf03ea8632c2b2799e79e088978235109d7","datavalue":{"value":"preemption","type":"string"},"datatype":"string"},"type":"statement","id":"Q507314$716F897B-D1B4-4844-82A5-D1467F2A9F9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"29ff25105b561b670176510ce616a966ffef4c26","datavalue":{"value":"unrelated machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q507314$728AA44E-3ADF-473D-BDC9-DECFE795B1B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c01a51105b1602eb458a8a0d5669470424318df0","datavalue":{"value":"\\(\\mathcal{APX}\\)-hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q507314$E34A5BA6-C419-4187-BC46-D0442E10F7FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0de600cf8191fa1f423fd01c9a02b172072a7391","datavalue":{"value":"approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q507314$38BB19DD-D6A8-417C-97C0-5111C0DE84EB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4359b37f4e8bf45d0a44d10ad36ba0ef291602ae","datavalue":{"value":{"entity-type":"item","numeric-id":1304485,"id":"Q1304485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507314$AB84398B-17D3-4588-87FC-0C2A867DCE36","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":"Q507314$BF4E4D48-5781-45A8-A1BE-9365B732214E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d46a5e216665e3588d496cfb3a43a1735e6a1cae","datavalue":{"value":"https://doi.org/10.1007/s10107-016-1004-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q507314$59DD73A4-F98A-4019-83FA-253C96D012B5","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3e48a25fb8f41fdc2866f215fb1902e06b4cec93","datavalue":{"value":"W2340234317","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q507314$A34CE3D2-3B39-4DA9-8326-DA2FF11B4038","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ec090966ae9a9392fa4a8efa8184abb7c9300c7","datavalue":{"value":{"entity-type":"item","numeric-id":3196615,"id":"Q3196615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507314$A0331CEF-8FE3-487D-86EE-EF9A6CA0434E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1051866b37a942eefb0bed17db919c0d3bc5ff6d","datavalue":{"value":{"entity-type":"item","numeric-id":2489956,"id":"Q2489956"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507314$C09B0D69-FF96-4A9A-B5B4-22D9D734B30B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cc52e5fd73d3b2f0935b0c4b7164d9dab1788fd3","datavalue":{"value":{"entity-type":"item","numeric-id":4769981,"id":"Q4769981"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507314$93EBE490-2B7A-4EE9-A9A9-3FA140105EE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9504ab4cd44c3274aee9ef0a9b25bd3449cff938","datavalue":{"value":{"entity-type":"item","numeric-id":4535067,"id":"Q4535067"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507314$B1C8A770-9CC1-4A8A-A153-3A8898E10254","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"809a9f827119a1a7d9cead9f3ff240c54a485c59","datavalue":{"value":{"entity-type":"item","numeric-id":5501838,"id":"Q5501838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507314$86D7611E-8B72-40F3-99E6-3E402CF9C942","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"864aa90b180e1c1166cb27aab62e39e47d6494b0","datavalue":{"value":{"entity-type":"item","numeric-id":2784510,"id":"Q2784510"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507314$D58125C6-9E0A-44F9-B313-5326B3975FCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dfbd785c98ffff9164411c97d0cfacab892ef9ed","datavalue":{"value":{"entity-type":"item","numeric-id":4111095,"id":"Q4111095"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507314$0C05D99F-096F-490E-8799-045A1EEB79E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"206aac1fed08722358479159401448a8a87bf332","datavalue":{"value":{"entity-type":"item","numeric-id":4198327,"id":"Q4198327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507314$C128028B-4817-49E9-B28E-2CC871A576D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c901734bd579355a7ba64889250fe648f0722302","datavalue":{"value":{"entity-type":"item","numeric-id":4875178,"id":"Q4875178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507314$8E9F7DA6-408D-46CD-82CE-CDF18E064A41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11b96895e61f4c8092d31e8b7e350b11769a103b","datavalue":{"value":{"entity-type":"item","numeric-id":2884502,"id":"Q2884502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507314$A80D0259-851E-4913-8F23-416FC581F8AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c01f4d5b60a35d0398264f1962552357860bfe6b","datavalue":{"value":{"entity-type":"item","numeric-id":5675148,"id":"Q5675148"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507314$8539E55F-0631-426F-A4F4-CA3316D3AA49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"429924f0ddd3bc1c7dc54a3226f108e3ebc2b532","datavalue":{"value":{"entity-type":"item","numeric-id":922700,"id":"Q922700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507314$3EB9D035-ED99-43CF-A118-6B450745C99C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"961f113f1ccc28206afcbc9ba1fbdfc17d641918","datavalue":{"value":{"entity-type":"item","numeric-id":4170215,"id":"Q4170215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507314$F370472B-F2EC-48DE-8257-0B890AEC6DFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2c5eaee631a4ae66b94907f207cf714150cffb0","datavalue":{"value":{"entity-type":"item","numeric-id":5470732,"id":"Q5470732"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507314$AED793A0-18B1-4D56-8181-0E99781D7890","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5ed0837e3d2395f7208cd800a53b0828b1bf078","datavalue":{"value":{"entity-type":"item","numeric-id":4806607,"id":"Q4806607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507314$E00D82E0-8D6D-49BA-96D1-6C56D7F3CCD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff5faec7978823cbd1765d0fad10943ba0529d1a","datavalue":{"value":{"entity-type":"item","numeric-id":4785695,"id":"Q4785695"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507314$CF71EDF4-4470-41FE-B8D8-25E5D05FE0F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"95bc4c69d5b6b7280aefc23d4c70a27d968a3585","datavalue":{"value":{"entity-type":"item","numeric-id":1806342,"id":"Q1806342"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507314$CBA2403C-025C-47A6-BF22-7ABAD89056E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"201daacb7a2a7f994c544bde561db6a6a6f2b7bd","datavalue":{"value":{"entity-type":"item","numeric-id":3541134,"id":"Q3541134"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507314$50F47A28-F94F-4700-B53F-04BE728011A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"44f4df5ec6a2c219ab15c25ec15f3bd93d291a5a","datavalue":{"value":{"entity-type":"item","numeric-id":5704855,"id":"Q5704855"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507314$7D772582-AC6D-47B6-B9A8-59F8BACDAF2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a40edf2cdb517563da91ef22a0b41ad003676966","datavalue":{"value":{"entity-type":"item","numeric-id":2819573,"id":"Q2819573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507314$7FF9C637-25B2-48C3-8773-E4F16A844451","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"352c925ef3e3d2cfc1419dfd8a7b71ff9c435991","datavalue":{"value":"10.1007/S10107-016-1004-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q507314$1B209256-B1F9-40E2-A97B-7503757E959F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c663faaa8c9d1fd4db3e68c65cb3df85fe18bf9c","datavalue":{"value":{"entity-type":"item","numeric-id":3541134,"id":"Q3541134"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"76e1e476b25c04826e3e2c0d2a5bb1ac27cc0134","datavalue":{"value":{"amount":"+0.9444846510887146","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":"Q507314$39C7588B-C016-4184-937E-6B38EC940794","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f32b05c4c50e6c4516078de0e195c3271e27b6fe","datavalue":{"value":{"entity-type":"item","numeric-id":1592754,"id":"Q1592754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f581892119aa53827d74feda85e24a358cc097bb","datavalue":{"value":{"amount":"+0.8663756251335144","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":"Q507314$5166428F-A534-4729-81E8-5114A484F1D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"65926a5f28563874a56b491fddc893355e3d3a5e","datavalue":{"value":{"entity-type":"item","numeric-id":2719134,"id":"Q2719134"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8b11c93b39b3e82c0425e505e9127c2ca5d52c45","datavalue":{"value":{"amount":"+0.8657539486885071","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":"Q507314$AE8C44C4-2811-4BB6-B9AA-52C1F00E26C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7a2b92d8beb47a8dd835183d984d540c91a314d6","datavalue":{"value":{"entity-type":"item","numeric-id":4535070,"id":"Q4535070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d8f63f9c47eea69fbe30b66e9beffb7f965a91b7","datavalue":{"value":{"amount":"+0.8446323871612549","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":"Q507314$C2B72A70-20FD-4B52-8598-1908FFA52C59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dbe03b1940769e733ae6a6bd9829fb1cc816b045","datavalue":{"value":{"entity-type":"item","numeric-id":1592284,"id":"Q1592284"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2417905c910d1c4b1c98f0304001a91028f1816c","datavalue":{"value":{"amount":"+0.8431817293167114","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":"Q507314$17CF8FCB-3841-4756-BE3E-E8C96F2A8DE6","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":"Q507314$E5F7D5B4-5FC3-4CA1-A192-3CD22D0A1178","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Approximability of average completion time scheduling on unrelated machines","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Approximability_of_average_completion_time_scheduling_on_unrelated_machines"}}}}}