ECCC
Electronic Colloquium on Computational Complexity
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 approximation schemes ... more >>>



ISSN 1433-8092 | Imprint