Inability of a graph neural network heuristic to outperform greedy algorithms in solving combinatorial optimization problems

被引：16

作者：

Boettcher, Stefan ^{[1
]}

机构：

[1] Emory Univ, Dept Phys, Atlanta, GA 30322 USA

来源：

NATURE MACHINE INTELLIGENCE | 2023年 / 5卷 / 01期

关键词：

D O I：

10.1038/s42256-022-00587-0

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

引用

页码：24 / 25

页数：2

共 11 条

[1]

Angelini M.C., 2022, ARXIV, DOI DOI 10.48550/ARXIV.2206.13211

[2] Numerical results for ground states of spin glasses on Bethe lattices [J].

Boettcher, S .

EUROPEAN PHYSICAL JOURNAL B, 2003, 31 (01) :29-39

[3] Analysis of the relation between quadratic unconstrained binary optimization and the spin-glass ground-state problem [J].

Boettcher, Stefan .

PHYSICAL REVIEW RESEARCH, 2019, 1 (03)

[4] Ground State Properties of the Diluted Sherrington-Kirkpatrick Spin Glass [J].

Boettcher, Stefan .

PHYSICAL REVIEW LETTERS, 2020, 124 (17)

[5] Simulations of ground state fluctuations in mean-field Ising spin glasses [J].

Boettcher, Stefan .

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT, 2010,

[6] EXTREMAL CUTS OF SPARSE RANDOM GRAPHS [J].

Dembo, Amir ;

Montanari, Andrea ;

Sen, Subhabrata .

ANNALS OF PROBABILITY, 2017, 45 (02) :1190-1217

[7] The cavity method at zero temperature [J].

Mézard, M ;

Parisi, G .

JOURNAL OF STATISTICAL PHYSICS, 2003, 111 (1-2) :1-34

[8] MEAN-FIELD THEORY OF RANDOMLY FRUSTRATED SYSTEMS WITH FINITE CONNECTIVITY [J].

MEZARD, M ;

PARISI, G .

EUROPHYSICS LETTERS, 1987, 3 (10) :1067-1074

[9] A SEQUENCE OF APPROXIMATED SOLUTIONS TO THE S-K MODEL FOR SPIN-GLASSES [J].

PARISI, G .

JOURNAL OF PHYSICS A-MATHEMATICAL AND GENERAL, 1980, 13 (04) :L115-L121

[10] Combinatorial optimization with physics-inspired graph neural networks [J].

Schuetz, Martin J. A. ;

Brubaker, J. Kyle ;

Katzgraber, Helmut G. .

NATURE MACHINE INTELLIGENCE, 2022, 4 (04) :367-377

← 1 2 →