An improved lower bound for rank four scheduling

Lin Chen, Deshi Ye, Guochuan Zhang

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


We consider the classical minimum makespan scheduling problem, where the processing time of job j on machine i is pij, and the matrix P=( pij)m×n is of a low rank. It is proved in Bhaskara et al. (2013) that rank 7 scheduling is NP-hard to approximate to a factor of 3/2-∈, and rank 4 scheduling is APX-hard (a factor of 1.03-∈). We improve this result by showing that rank 4 scheduling is already NP-hard to approximate within a factor of 3/2-∈ .

Original languageEnglish
Pages (from-to)348-350
Number of pages3
JournalOperations Research Letters
Issue number5
StatePublished - Jul 2014


  • APX-hardness
  • Complexity
  • Scheduling


Dive into the research topics of 'An improved lower bound for rank four scheduling'. Together they form a unique fingerprint.

Cite this