USING DUAL APPROXIMATION ALGORITHMS FOR SCHEDULING PROBLEMS - THEORETICAL AND PRACTICAL RESULTS

被引：487

作者：

HOCHBAUM, DS ^{[1
]}

SHMOYS, DB ^{[1
]}

机构：

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

来源：

关键词：

D O I：

10.1145/7531.7535

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

引用

页码：144 / 162

页数：19

共 12 条

[1]

[Anonymous], 1969, SIAM J APPL MATH

[2]

COFFMAN EG, 1978, SIAM J COMPUT, V7, P1, DOI 10.1137/0207001

[3]

DELAVEGA WF, 1981, COMBINATORICA, V1, P349

[4] TIGHTER BOUNDS FOR THE MULTIFIT PROCESSOR SCHEDULING ALGORITHM [J].

FRIESEN, DK .

[5]

FRIESEN DK, 1978, UIUCDCSR78939 U ILL

[6]

Garey MR., 1979, COMPUTERS INTRACTABI

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

GRAHAM, RL .

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

HOCHBAUM, DS ;

SHMOYS, DB .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1986, 7 (02) :247-257

[9]

Karmarkar N., 1982, 23rd Annual Symposium on Foundations of Computer Science, P312, DOI 10.1109/SFCS.1982.61

[10]

LANGSTON MA, 1981, THESIS TEXAS A M U