{"entities":{"Q1736801":{"pageid":1747542,"ns":120,"title":"Item:Q1736801","lastrevid":56712138,"modified":"2026-03-19T02:59:36Z","type":"item","id":"Q1736801","labels":{"en":{"language":"en","value":"A 3/2-approximation algorithm for the graph balancing problem with two weights"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7042347"}},"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":"Q1736801$7160E4D7-712F-447F-B0BD-94016838DFD2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"bf4129646fb5896ddf87e5b3da61da67fce8b5ac","datavalue":{"value":{"text":"A 3/2-approximation algorithm for the graph balancing problem with two weights","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1736801$FDA672C4-2EA1-4925-944F-133CF1A7E21E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"702e3e5b0e5fe9e832128b85fb8eaaf9db13baa1","datavalue":{"value":"1461.05218","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736801$6FB4F258-C9EB-4E4C-82CA-AD1044D26602","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"82394b359330b505969b713f6bf78f79ed5640eb","datavalue":{"value":{"entity-type":"item","numeric-id":387318,"id":"Q387318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736801$F3B55656-D638-4506-8186-1984599C8AC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d20669dfd1f646f116bdcd4edb829ffbf240e456","datavalue":{"value":{"entity-type":"item","numeric-id":203725,"id":"Q203725"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736801$55BEB811-D8E0-4E61-A30D-E1676368B128","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"18e3aed7ec2baba1bc6b2c08988b16bb9ac0e77f","datavalue":{"value":{"entity-type":"item","numeric-id":82263,"id":"Q82263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736801$674A5AA6-3C9A-48F7-85DB-F772C87D0B63","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d660e31d569d3203bec6d5e897b7f6ed7f6a3a72","datavalue":{"value":{"time":"+2019-03-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1736801$8CD84CC3-A5E3-4DDE-BD88-8E76AE679B23","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8a6eadac7e0e80db1ef30682e89f967ac801b255","datavalue":{"value":"Summary: In the pursuit of finding subclasses of the makespan minimization problem on unrelated parallel machines that have approximation algorithms with approximation ratio better than 2, the graph balancing problem has been of current interest. In the graph balancing problem each job can be non-preemptively scheduled on one of at most two machines with the same processing time on either machine. Recently, \\textit{T. Ebenlendr} et al. [Algorithmica 68, No. 1, 62--80 (2014; Zbl 1295.68214)] presented a \\(7/4\\)-approximation algorithm for the graph balancing problem. Let \\(r\\), \\(s \\in \\mathbb Z^+\\). In this paper we consider the graph balancing problem with two weights, where a job either takes \\(r\\) time units or \\(s\\) time units. We present a \\(3/2\\)-approximation algorithm for this problem. This is an improvement over the previously best-known approximation algorithm for the problem with approximation ratio 1.652 and it matches the best known inapproximability bound for it.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736801$E19D7D0A-E843-4761-B790-0B31C3DD8A33","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736801$A5CDEA7D-7BE7-40AF-BE50-3BC8BBC217CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736801$6997074A-5A7F-4CAF-A6CF-4FBD8E0F3F1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736801$7CF1FBCA-60EB-4E0A-8B0D-E98E65E1D3A8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8a516e4809fcc5309f908abfdd5a304e7908ce79","datavalue":{"value":"7042347","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736801$86D4965C-FB2C-43CA-BAEC-7D21E4EA064F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc4837877785b4675d8ac1c6d4c911bcaf794e13","datavalue":{"value":"approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736801$64AC8F96-A1EC-4C59-8D0B-24BF0CCDD60B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0605a1f2800486f9350885e9d3e822d311d76006","datavalue":{"value":"scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736801$DE0EAE88-CD14-4A20-9752-C49A94EC6697","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5e61975bf3b637d51a9d30b7e2b6941b7575cf64","datavalue":{"value":"graph balancing problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736801$44AA5164-D13F-46D2-A821-484E6DD089CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b1b56b194e4c60843b06da9b24daca40acbfb290","datavalue":{"value":"restricted assignment problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736801$0344E811-E72F-4372-AD2C-326964072B27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"72bf1bd12f072b8ea4bb41164d8dbc33d014dfd3","datavalue":{"value":"makespan minimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736801$791CB4BA-62E6-4E05-A859-AF6BB5D75586","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":"Q1736801$87106675-E518-426A-8144-7785DB2CE800","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9a9a1ef05b5cfa7098d5d8b26ac4483638e73ce6","datavalue":{"value":"https://doi.org/10.3390/a9020038","type":"string"},"datatype":"url"},"type":"statement","id":"Q1736801$CD0CBCE0-A743-447A-8AA4-F19B662810E3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a0f1ae8a25cb63b47f1d26c0f81432f814530bb2","datavalue":{"value":"W2412591217","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736801$FA25D9C5-A2F4-40B2-9822-5698415AEF32","rank":"normal"}],"P223":[{"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":"Q1736801$15F5513F-7503-47BB-832A-9622A3097E00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c2b3c7fb3b376eb72f67f57977bbae27ac2eaac","datavalue":{"value":{"entity-type":"item","numeric-id":751989,"id":"Q751989"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736801$D802A0D2-7DB5-4595-9970-9F19C40B86D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"abfe2bea98e52a87325c52c8ceb6e55ee50380fb","datavalue":{"value":{"entity-type":"item","numeric-id":2488212,"id":"Q2488212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736801$E893C0C5-39C8-43E8-871D-BE761E182C1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f7d5b96c1a874ace8931a55d299cd1dd0249b22","datavalue":{"value":{"entity-type":"item","numeric-id":2373738,"id":"Q2373738"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736801$5F17E8B6-8F5C-493C-B4E2-4F14E061358C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bebae2cac5ad95279fccfd2dfd7e9462f8040a43","datavalue":{"value":{"entity-type":"item","numeric-id":543514,"id":"Q543514"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736801$1E7E0380-76B8-45FE-8A83-54984DBF2450","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c6fc1576fe1840138383f7a3a99f7a1881c9583","datavalue":{"value":{"entity-type":"item","numeric-id":5363001,"id":"Q5363001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736801$BAE9C6AC-3D55-428E-AE4E-D6CF76E7588A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"40bdc5594ecbeee5cf09163c3d5251a4a043c488","datavalue":{"value":{"entity-type":"item","numeric-id":2441586,"id":"Q2441586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736801$20B3E5FB-D107-41D7-84A8-D2411765BBC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"130a3da284a7a2861289aa35a6e95d2d0de5d506","datavalue":{"value":{"entity-type":"item","numeric-id":990093,"id":"Q990093"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736801$B5C4ACDF-EC02-4612-8BDA-8A218DC8DC86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4eda9fed443585e71e844bfa879dcda55a1500c9","datavalue":{"value":{"entity-type":"item","numeric-id":1941692,"id":"Q1941692"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736801$3C5BAC80-B377-4B36-B616-CE8CDFBB7DE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"419432817d000c4dbc5236265aeb376a56f51e50","datavalue":{"value":{"entity-type":"item","numeric-id":490331,"id":"Q490331"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736801$95AC7F85-68CF-4E09-AE2A-1A28E6CF1081","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e24078b61f81acc3be036e892fc6f98c660d5405","datavalue":{"value":{"entity-type":"item","numeric-id":3579372,"id":"Q3579372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736801$33766A18-9190-4F78-9FE7-3921D9C2E012","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab173f70b373d92a813f1239c444ea63b8c231f6","datavalue":{"value":{"entity-type":"item","numeric-id":5434435,"id":"Q5434435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736801$BCB809C3-4BAA-4494-9DBC-5CAE3F3D1FD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4534d792f5262a1f297a74f9b43efedcc5cd94ec","datavalue":{"value":{"entity-type":"item","numeric-id":4760022,"id":"Q4760022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736801$8733EF0B-3C90-4039-864E-AD7E797A0CAA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ecf792aa783219b80f4a38a40ac8a859604d78a3","datavalue":{"value":"10.3390/A9020038","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736801$FA83C6D4-F627-43A5-8F8B-55B9DE048C2D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"34bccd6e7061c035baac8ee89959ed4eda0a100c","datavalue":{"value":{"entity-type":"item","numeric-id":2424664,"id":"Q2424664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4edb633f8240622495725ccb62afd6efdce84120","datavalue":{"value":{"amount":"+0.8802202343940735","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":"Q1736801$9E01C4D5-D5EE-46A1-AB98-94D634B9B4EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e19ee22ac0302b8af4a5e70eb16b4e06700b18c1","datavalue":{"value":{"entity-type":"item","numeric-id":2441586,"id":"Q2441586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"080af201ed54fdae6b408d6477fdd3b36c66fa8c","datavalue":{"value":{"amount":"+0.8676402568817139","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":"Q1736801$ED62B115-2FF3-4B46-B305-BA91D1BD819D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f6238c22687d6396640d7f078fc20bc7e0e9f567","datavalue":{"value":{"entity-type":"item","numeric-id":4606320,"id":"Q4606320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e16a14a16279f14e7eb071f890a8ce9615c687bc","datavalue":{"value":{"amount":"+0.8648508787155151","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":"Q1736801$C68147E1-86E5-426C-B284-B81CFBBC5318","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"08bfb3b35bade399b85c7b14fa8ae3e84a894596","datavalue":{"value":{"entity-type":"item","numeric-id":6049079,"id":"Q6049079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a61b7104281446eb716b10501f3bb71bf6f5a18c","datavalue":{"value":{"amount":"+0.8624796867370605","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":"Q1736801$156AB8AD-A74E-4113-B54C-D0FCCA356803","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e084b19bc102b6c6431ed9684703c0fce398da2c","datavalue":{"value":{"entity-type":"item","numeric-id":2173300,"id":"Q2173300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b8c03029dde2ba41f1f2bfd19fffeb083aa21ac","datavalue":{"value":{"amount":"+0.7856166362762451","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":"Q1736801$DF025461-5E99-4261-9AF9-C4088D63D2FD","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":"Q1736801$259DD4B2-C8D8-4F3F-ADBB-EA21ECBB75C7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1736801","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1736801"}}}}}