2026-08-06T13:01:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18830 2024-03-06T11:02:40Z ddc:004 open_access

Approximation Algorithms for Maximum Weighted Throughput on Unrelated Machines Karakostas, George Kolliopoulos, Stavros G. scheduling maximum weighted throughput unrelated machines approximation algorithm PTAS We study the classic weighted maximum throughput problem on unrelated machines. We give a (1-1/e-ε)-approximation algorithm for the preemptive case. To our knowledge this is the first ever approximation result for this problem. It is an immediate consequence of a polynomial-time reduction we design, that uses any ρ-approximation algorithm for the single-machine problem to obtain an approximation factor of (1-1/e)ρ -ε for the corresponding unrelated-machines problem, for any ε > 0. On a single machine we present a PTAS for the non-preemptive version of the problem for the special case of a constant number of distinct due dates or distinct release dates. By our reduction this yields an approximation factor of (1-1/e) -ε for the non-preemptive problem on unrelated machines when there is a constant number of distinct due dates or release dates on each machine. Schloss Dagstuhl – Leibniz-Zentrum für Informatik George Karakostas and Stavros G. Kolliopoulos 2023 Is Part Of LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2023.5 urn:nbn:de:0030-drops-188305 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.5 eng https://creativecommons.org/licenses/by/4.0/legalcode