A neural network for the minimum set covering problem

被引：9

作者：

Hifi, M

Paschos, VT

Zissimopoulos, V

机构：

[1] Univ Paris 09, LAMSADE, F-75775 Paris 16, France

[2] Univ Paris 01, CERMSEM, F-75231 Paris, France

[3] Univ Paris 13, LIPN, Paris, France

来源：

CHAOS SOLITONS & FRACTALS | 2000年 / 11卷 / 13期

关键词：

D O I：

10.1016/S0960-0779(99)00104-6

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We solve approximately the weighted set covering problem by putting together a neural network model, the Boltzmann machine (BM), and some combinatorial ideas. We compare the solutions provided by the network with the ones obtained using the greedy set covering heuristic and the Lagrangian heuristic developed by Beasley. Moreover, we use a simple and intuitive polynomial decomposition scheme treating large instances by decomposing them into smaller ones. Finally, we report on the relation between the convergence time of the model and the size of the instances of set covering. (C) 2000 Elsevier Science Ltd. All rights reserved.

引用

页码：2079 / 2089

页数：11

共 25 条

[11] Bruck J., 1990, Journal of Complexity, V6, P129, DOI 10.1016/0885-064X(90)90001-T
[12] Christofides N., 1993, Annals of Operations Research, V43, P261
[13] Chvatal V., 1979, Mathematics of Operations Research, V4, P233, DOI 10.1287/moor.4.3.233
[14] JACOBS LW, 1995, NAV RES LOG, V42, P1129, DOI 10.1002/1520-6750(199510)42:7<1129::AID-NAV3220420711>3.0.CO
[15] 2-M
[16] APPROXIMATION ALGORITHMS FOR COMBINATORIAL PROBLEMS
JOHNSON, DS
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1974, 9 (03) : 256 - 278
[17] Group updates and multiscaling: An efficient neural network approach to combinatorial optimization
Likas, A
Stafylopatis, A
[J]. IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART B-CYBERNETICS, 1996, 26 (02): : 222 - 232
[18] PAPADIMITRIOU CH, 1981, COMBINATORIAL OPTIMI
[19] Raz R., 1997, P 29 ANN ACM S THEOR, P475, DOI [10.1145/258533.258641, 10.1145/258533.2586418, DOI 10.1145/258533.2586418]
[20] Rumelhart D. E., 1986, PDP RES GROUP PARALL, V1, P110

← 1 2 3 →