STATISTICAL-MECHANICS OF THE KNAPSACK-PROBLEM

被引：14

作者：

KORUTCHEVA, E ^{[1
]}

OPPER, M ^{[1
]}

LOPEZ, B ^{[1
]}

机构：

[1] G NADJAKOV INST SOLID STATE PHYS,BU-1784 SOFIA,BULGARIA

来源：

JOURNAL OF PHYSICS A-MATHEMATICAL AND GENERAL | 1994年 / 27卷 / 18期

关键词：

D O I：

10.1088/0305-4470/27/18/001

中图分类号：

O4 [物理学];

学科分类号：

0702 ;

摘要：

The knapsack problem is an NP-complete combinatorial optimization problem with inequality constraints. Using the replica method of statistical physics, we study the space of its solutions for a large problem size. It turns out that this problem is closely related to the theory of the binary perceptron.

引用

页码：L645 / L650

页数：6

共 12 条

[1] STABILITY OF SHERRINGTON-KIRKPATRICK SOLUTION OF A SPIN GLASS MODEL [J].

DEALMEIDA, JRL ;

THOULESS, DJ .

JOURNAL OF PHYSICS A-MATHEMATICAL AND GENERAL, 1978, 11 (05) :983-990

[2] THE STATISTICAL-MECHANICS OF THE ISING PERCEPTRON [J].

FONTANARI, JF ;

MEIR, R .

JOURNAL OF PHYSICS A-MATHEMATICAL AND GENERAL, 1993, 26 (05) :1077-1089

[3] APPLICATION OF STATISTICAL-MECHANICS TO NP-COMPLETE PROBLEMS IN COMBINATORIAL OPTIMIZATION [J].

FU, YT ;

ANDERSON, PW .

JOURNAL OF PHYSICS A-MATHEMATICAL AND GENERAL, 1986, 19 (09) :1605-1620

[4] OPTIMAL STORAGE PROPERTIES OF NEURAL NETWORK MODELS [J].

GARDNER, E ;

DERRIDA, B .

JOURNAL OF PHYSICS A-MATHEMATICAL AND GENERAL, 1988, 21 (01) :271-284

[5]

Garey M.R., 1979, COMPUTERS INTRACTABI, V174

[6] STORAGE CAPACITY OF MEMORY NETWORKS WITH BINARY COUPLINGS [J].

KRAUTH, W ;

MEZARD, M .

JOURNAL DE PHYSIQUE, 1989, 50 (20) :3057-3066

[7] A REPLICA ANALYSIS OF THE TRAVELING SALESMAN PROBLEM [J].

MEZARD, M ;

PARISI, G .

JOURNAL DE PHYSIQUE, 1986, 47 (08) :1285-1296

[8]

MEZARD M, J PHYSIQUE LETT, V46, pL771

[9]

MEZARD M, 1987, LECTURES NOTES PHYSI, V9

[10]

OHLSSON M, COMMUNICATION

← 1 2 →