A tutorial on complexity

Joseph Y.T. Leung

Research output: Chapter in Book/Report/Conference proceedingChapter


Complexity theory is an important tool in scheduling research. When we are confronted with a new scheduling problem, the very first thing we try is to develop efficient algorithms for solving the problem. Unfortunately, very often, we could not come up with any algorithm more efficient than essentially an enumerative search, even though a considerable amount of time had been spent on the problem. In situations like this, the theory of NP-hardness may be useful to pinpoint that no efficient algorithms could possibly exist for the problem in hand. Therefore, knowledge of NP-hardness is absolutely essential for anyone interested in scheduling research.

Original languageEnglish (US)
Title of host publicationHandbook of Scheduling
Subtitle of host publicationAlgorithms, Models, and Performance Analysis
PublisherCRC Press
ISBN (Electronic)9780203489802
ISBN (Print)9781584883975
StatePublished - Jan 1 2004

All Science Journal Classification (ASJC) codes

  • General Engineering
  • General Computer Science
  • General Economics, Econometrics and Finance
  • General Business, Management and Accounting


Dive into the research topics of 'A tutorial on complexity'. Together they form a unique fingerprint.

Cite this