Randomized methods for the number partitioning problem

被引：16

作者：

Arguello, MF ^{[1
]}

Feo, TA ^{[1
]}

Goldschmidt, O ^{[1
]}

机构：

[1] UNIV TEXAS,DEPT MECH ENGN,OPERAT RES GRP,AUSTIN,TX 78712

来源：

COMPUTERS & OPERATIONS RESEARCH | 1996年 / 23卷 / 02期

关键词：

D O I：

10.1016/0305-0548(95)E0020-L

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

Randomized versions of Karmarkar and Karp's differencing method are introduced for the Number Partitioning problem. The development of these methods and a discussion of their merits are presented. It is shown that these randomized heuristics consistently yield better solutions than those generated by the differencing method.

引用

页码：103 / 111

页数：9

共 10 条

[1]

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

[2]

ARGUELLO MF, 1992, THESIS U TEXAS AUSTI

[3] A GRASP-STAR FOR A DIFFICULT SINGLE-MACHINE SCHEDULING PROBLEM [J].

FEO, TA ;

VENKATRAMAN, K ;

BARD, JF .

COMPUTERS & OPERATIONS RESEARCH, 1991, 18 (08) :635-643

[4]

FEO TA, 1990, GREEDY RANDOMIZED AD

[5]

FEO TA, 1988, OPER RES LETT, V8, P767

[6] OPTIMIZATION BY SIMULATED ANNEALING - AN EXPERIMENTAL EVALUATION .2. GRAPH-COLORING AND NUMBER PARTITIONING [J].

JOHNSON, DS ;

ARAGON, CR ;

MCGEOCH, LA ;

SCHEVON, C .

OPERATIONS RESEARCH, 1991, 39 (03) :378-406

[7] PROBABILISTIC ANALYSIS OF OPTIMUM PARTITIONING [J].

KARMARKAR, N ;

KARP, RM ;

LUEKER, GS ;

ODLYZKO, AM .

JOURNAL OF APPLIED PROBABILITY, 1986, 23 (03) :626-645

[8]

KARMARKAR N, 1982, UCBCSD82113 U CAL BE

[9]

Papadimitriou C H., 1982, Combinatorial optimization: algorithms and complexity

[10]

SMITH SH, 1990, GRASP COLORING SPARS

← 1 →