Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR00-007 | 14th December 1999 00:00

Randomized Approximation Schemes for Scheduling Unrelated Parallel Machines



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.

ISSN 1433-8092 | Imprint