A POLYNOMIAL-APPROXIMATION SCHEME FOR SCHEDULING ON UNIFORM PROCESSORS - USING THE DUAL APPROXIMATION APPROACH

被引：219

作者：

HOCHBAUM, DS ^{[1
]}

SHMOYS, DB ^{[1
]}

机构：

[1] MIT,DEPT MATH,CAMBRIDGE,MA 02139

来源：

关键词：

D O I：

10.1137/0217033

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

引用

页码：539 / 551

页数：13

共 9 条

[1] BOUNDS FOR LIST SCHEDULES ON UNIFORM PROCESSORS [J].

CHO, Y ;

SAHNI, S .

[2] BOUNDS FOR MULTIFIT SCHEDULING ON UNIFORM PROCESSORS [J].

FRIESEN, DK ;

LANGSTON, MA .

[3]

Garey MR., 1979, COMPUTERS INTRACTABI

[4]

Gonzalez T., 1977, SIAM Journal on Computing, V6, P155, DOI 10.1137/0206013

[5]

Graham R. L., 1979, Discrete Optimisation, P287

[6] BOUNDS FOR CERTAIN MULTIPROCESSING ANOMALIES [J].

GRAHAM, RL .

BELL SYSTEM TECHNICAL JOURNAL, 1966, 45 (09) :1563-+

HOCHBAUM, DS ;

SHMOYS, DB .

HOROWITZ, E ;

SAHNI, S .

[9]

LIU JWS, 1974, INFORM PROCESSING, V74, P349