TR00-007 Authors: Pavlos S. Efraimidis, Paul Spirakis

Publication: 8th February 2000 15:17

Downloads: 1672

Keywords:

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.