An improved lower bound for rank four scheduling

Lin Chen; Deshi Ye; Guochuan Zhang

doi:10.1016/j.orl.2014.06.003

An improved lower bound for rank four scheduling

Lin Chen, Deshi Ye, Guochuan Zhang

Computer Science

Research output: Contribution to journal › Article › peer-review

9 Scopus citations

Abstract

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 language	English
Pages (from-to)	348-350
Number of pages	3
Journal	Operations Research Letters
Volume	42
Issue number	5
DOIs	https://doi.org/10.1016/j.orl.2014.06.003
State	Published - Jul 2014

Keywords

APX-hardness
Complexity
Scheduling

Access to Document

10.1016/j.orl.2014.06.003

Cite this

@article{0fc36c38b6f6487a8a93c5f2206dfc23,

title = "An improved lower bound for rank four scheduling",

abstract = "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-∈ .",

keywords = "APX-hardness, Complexity, Scheduling",

author = "Lin Chen and Deshi Ye and Guochuan Zhang",

note = "Funding Information: The research of the second author is supported in part by NSFC ( 11071215 ). The research of the third author is supported in part by NSFC ( 11271325 ). ",

year = "2014",

month = jul,

doi = "10.1016/j.orl.2014.06.003",

language = "English",

volume = "42",

pages = "348--350",

journal = "Operations Research Letters",

issn = "0167-6377",

number = "5",

}

TY - JOUR

T1 - An improved lower bound for rank four scheduling

AU - Chen, Lin

AU - Ye, Deshi

AU - Zhang, Guochuan

N1 - Funding Information: The research of the second author is supported in part by NSFC ( 11071215 ). The research of the third author is supported in part by NSFC ( 11271325 ).

PY - 2014/7

Y1 - 2014/7

N2 - 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-∈ .

AB - 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-∈ .

KW - APX-hardness

KW - Complexity

KW - Scheduling

UR - http://www.scopus.com/inward/record.url?scp=84903272460&partnerID=8YFLogxK

U2 - 10.1016/j.orl.2014.06.003

DO - 10.1016/j.orl.2014.06.003

M3 - Article

AN - SCOPUS:84903272460

SN - 0167-6377

VL - 42

SP - 348

EP - 350

JO - Operations Research Letters

JF - Operations Research Letters

IS - 5

ER -

An improved lower bound for rank four scheduling

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this