Exécution de notre outil de synthèse sur un nouvel article
Vérifiez l’article ci-dessous, puis lancez sa synthèse.
Approximation algorithms for maximum weighted throughput on unrelated machines
George Karakostas (McMaster University), Stavros G. Kolliopoulos (National and Kapodistrian University of Athens)
Résumé : We study the classic weighted maximum throughput problem on unrelated machines. We give a ( 1 − 1 / e − ε ) -approximation algorithm for the preemptive case with no migrations. 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 . The reduction works both for the preemptive and the non-preemptive setting. 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.