On optimality of exact and approximation algorithms for scheduling problems

We consider the classical scheduling problem on parallel identical machines to minimize the makespan. Under the exponential time hypothesis (ETH), lower bounds on the running times of exact and approximation algorithms are characterized.

Logo BII

Rights

Use and reproduction:

No license. The provisions of the German Copyright Act (UrhG) apply.

Please note that individual components of the publication may be subject to other licensing or copyright conditions.

Cite

Citation style:
Could not load citation form.