ECCC-Report TR00-007https://eccc.weizmann.ac.il/report/2000/007Comments and Revisions published for TR00-007en-usTue, 08 Feb 2000 15:17:15 +0200
Paper TR00-007
| Randomized Approximation Schemes for Scheduling Unrelated Parallel Machines |
Pavlos S. Efraimidis,
Paul Spirakis
https://eccc.weizmann.ac.il/report/2000/007
The problem of Scheduling $n$ Independent Jobs
on $m$ Unrelated Parallel Machines, when $m$
is fixed, is considered. The standard problem
of minimizing the makespan of the schedule
(SUM) and the bicriteria problem of scheduling
with bounded makespan and cost (SUMC), are
addressed, and randomized fully linear time
approximation schemes are shown for both
problems. The core of the algorithms is an
interesting new randomized rounding procedure,
the Filtered Randomized Rounding (FRR), that
boosts the deviation bounds of the rounded
linear packing constraints to any given
constant ratio. Finally, the notion of {\it
polybottleneck} combinatorial optimization
problems is defined and used to build $O(n
\log n \log\log n)$ time approximation schemes
for two natural optimization versions of SUMC
obtained by bounding the one objective and
optimizing the other. All algorithms admit
simple optimal work parallelization.
Tue, 08 Feb 2000 15:17:15 +0200https://eccc.weizmann.ac.il/report/2000/007