On the optimality of exact and approximation algorithms for scheduling problems

Lin Chen, Klaus Jansen, Guochuan Zhang

Research output: Contribution to journalArticle

4 Scopus citations

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.

Original languageEnglish
Pages (from-to)1-32
Number of pages32
JournalJournal of Computer and System Sciences
Volume96
DOIs
StatePublished - Sep 2018

Keywords

  • Approximation schemes
  • Exponential time hypothesis
  • Lower bounds
  • Scheduling

Fingerprint Dive into the research topics of 'On the optimality of exact and approximation algorithms for scheduling problems'. Together they form a unique fingerprint.

  • Cite this