Running summarizing tools on a new article
Check the paper below, then start its synthesis.
Approximation algorithms for maximum weighted throughput on unrelated machines
George Karakostas (McMaster University), Stavros G. Kolliopoulos (National and Kapodistrian University of Athens)
Abstract: 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.