An improved lower bound for rank four scheduling

被引：8

作者：

Chen, Lin ^{[1
]}

Ye, Deshi ^{[1
]}

Zhang, Guochuan ^{[1
]}

机构：

[1] Zhejiang Univ, Coll Comp Sci, Hangzhou, Zhejiang, Peoples R China

来源：

OPERATIONS RESEARCH LETTERS | 2014年 / 42卷 / 05期

关键词：

Complexity; APX-hardness; Scheduling; APPROXIMATION;

D O I：

10.1016/j.orl.2014.06.003

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We consider the classical minimum makespan scheduling problem, where the processing time of job j on machine i is p(ij), and the matrix P = (p(ij))(mxn) 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 - epsilon, and rank 4 scheduling is APX-hard (a factor of 1.03 - epsilon). We improve this result by showing that rank 4 scheduling is already NP-hard to approximate within a factor of 3/2 - epsilon. (C) 2014 Elsevier B.V. All rights reserved.

引用

页码：348 / 350

页数：3

共 8 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness

[2]

Bhaskara A, 2013, PROCEEDINGS OF THE TWENTY-FOURTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS (SODA 2013), P937

[3]

Chen L., 2014, Proceedings_of_the Twenty-Fifth_Annual_ACM-SIAM_Symposium_on_Discrete_Algorithms,_SODA 2014,_Portland,_Oregon,_USA,_January_5-7,_2014, P657

[4]

Chen L., 2013, ABS13063727 CORR

[5] A POLYNOMIAL-APPROXIMATION SCHEME FOR SCHEDULING ON UNIFORM PROCESSORS - USING THE DUAL APPROXIMATION APPROACH [J].

HOCHBAUM, DS ;

SHMOYS, DB .

SIAM JOURNAL ON COMPUTING, 1988, 17 (03) :539-551

[6] APPROXIMATION ALGORITHMS FOR SCHEDULING UNRELATED PARALLEL MACHINES [J].

LENSTRA, JK ;

SHMOYS, DB ;

TARDOS, E .

MATHEMATICAL PROGRAMMING, 1990, 46 (03) :259-271

[7] An optimal rounding gives a better approximation for scheduling unrelated machines [J].

Shchepin, EV ;

Vakhania, N .

OPERATIONS RESEARCH LETTERS, 2005, 33 (02) :127-133

[8] A SIMPLIFIED NP-COMPLETE SATISFIABILITY PROBLEM [J].

TOVEY, CA .

DISCRETE APPLIED MATHEMATICS, 1984, 8 (01) :85-89

← 1 →