W[2]-hardness of precedence constrained K-processor scheduling

Hans L. Bodlaender; Michael R. Fellows

W[2]-hardness of precedence constrained K-processor scheduling

Hans L. Bodlaender, Michael R. Fellows^*

^*Corresponding author for this work

Decision Support Systems

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

Abstract

It is shown that the Precedence Constrained K-Processor Scheduling problem is hard for the parameterized complexity class W[2]. This means that there does not exist a constant c, such that for all fixed K, the Precedence Constrained K-Processor Scheduling problem can be solved in O(n^c) time, unless an unlikely collapse occurs in the parameterized complexity hierarchy. That is, if the problem can be solved in polynomial time for each fixed K, then it is likely that the degree of the running time polynomial must increase as the number of processors K increases.

Original language	English
Pages (from-to)	93-97
Number of pages	5
Journal	Operations Research Letters
Volume	18
Issue number	2
Publication status	Published - 1 Sept 1995

Keywords

Multiprocessor scheduling
Parameterized complexity
Partial orders

Cite this

@article{8c6e5a6682d94d869bfe8448b6bbcd49,

title = "W[2]-hardness of precedence constrained K-processor scheduling",

abstract = "It is shown that the Precedence Constrained K-Processor Scheduling problem is hard for the parameterized complexity class W[2]. This means that there does not exist a constant c, such that for all fixed K, the Precedence Constrained K-Processor Scheduling problem can be solved in O(nc) time, unless an unlikely collapse occurs in the parameterized complexity hierarchy. That is, if the problem can be solved in polynomial time for each fixed K, then it is likely that the degree of the running time polynomial must increase as the number of processors K increases.",

keywords = "Multiprocessor scheduling, Parameterized complexity, Partial orders",

author = "Bodlaender, {Hans L.} and Fellows, {Michael R.}",

year = "1995",

month = sep,

day = "1",

language = "English",

volume = "18",

pages = "93--97",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier BV",

number = "2",

}

TY - JOUR

T1 - W[2]-hardness of precedence constrained K-processor scheduling

AU - Bodlaender, Hans L.

AU - Fellows, Michael R.

PY - 1995/9/1

Y1 - 1995/9/1

N2 - It is shown that the Precedence Constrained K-Processor Scheduling problem is hard for the parameterized complexity class W[2]. This means that there does not exist a constant c, such that for all fixed K, the Precedence Constrained K-Processor Scheduling problem can be solved in O(nc) time, unless an unlikely collapse occurs in the parameterized complexity hierarchy. That is, if the problem can be solved in polynomial time for each fixed K, then it is likely that the degree of the running time polynomial must increase as the number of processors K increases.

AB - It is shown that the Precedence Constrained K-Processor Scheduling problem is hard for the parameterized complexity class W[2]. This means that there does not exist a constant c, such that for all fixed K, the Precedence Constrained K-Processor Scheduling problem can be solved in O(nc) time, unless an unlikely collapse occurs in the parameterized complexity hierarchy. That is, if the problem can be solved in polynomial time for each fixed K, then it is likely that the degree of the running time polynomial must increase as the number of processors K increases.

KW - Multiprocessor scheduling

KW - Parameterized complexity

KW - Partial orders

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

M3 - Article

AN - SCOPUS:33646501232

SN - 0167-6377

VL - 18

SP - 93

EP - 97

JO - Operations Research Letters

JF - Operations Research Letters

IS - 2

ER -

W[2]-hardness of precedence constrained K-processor scheduling

Abstract

Keywords

Other files and links

Fingerprint

Cite this