Chen, Lin, Jansen, Klaus and Zhang, Guochuan (2018) On the optimality of exact and approximation algorithms for scheduling problems. Journal of Computer and System Sciences, 96 . pp. 1-32. DOI 10.1016/j.jcss.2018.03.005.

Full text not available from this repository.

Abstract

We consider the classical scheduling problem on parallel identical machines to minimize the makespan. There is a long history of study on this problem, focusing on exact and approximation algorithms. It is thus natural to consider whether these algorithms can be further improved in terms of running times. We provide strong lower bounds on the running times of exact and approximation schemes for the classical scheduling problem based on Exponential Time Hypothesis, showing that the best known approximation and exact algorithms are almost the best possible in terms of the running time.

Document Type:	Article
Keywords:	Approximation schemes, Scheduling, Lower bounds, Exponential time hypothesis
Research affiliation:	Kiel University > Kiel Marine Science OceanRep > The Future Ocean - Cluster of Excellence Kiel University
Refereed:	Yes
Open Access Journal?:	No
Publisher:	Elsevier
Projects:	Future Ocean
Date Deposited:	01 Aug 2018 09:12
Last Modified:	27 Mar 2019 08:59
URI:	https://oceanrep.geomar.de/id/eprint/43885

Actions (login required)

View Item