Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > RELAXED DECISION PROCEDURES:
Reports tagged with relaxed decision procedures:
TR00-007 | 14th December 1999
Pavlos S. Efraimidis, Paul Spirakis

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
more >>>




ISSN 1433-8092 | Imprint