Neural networks for NP-complete problems

DOI10.1016/S0362-546X(97)00308-8MaRDI QIDQ4377229zbMATH OpenFDO

Authors Marco Budinich

Publication date 7 September 1998

Published in Nonlinear Analysis: Theory, Methods & Applications (Search for Journal in Brave)

zbMATH Keywords

approximate solutionsneural networksNP-complete problems

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• On the power of neural networks for solving hard problems
• Neural network methods in combinatorial optimization
• Finding approximate solutions to NP-hard problems by neural networks is hard
• On problem solving with Hopfield neural networks

Cites work

• scientific article; zbMATH DE number 53096 (Why is no real title available?)
• scientific article; zbMATH DE number 177832 (Why is no real title available?)
• scientific article; zbMATH DE number 1057697 (Why is no real title available?)
• A study of the application of Kohonen-type neural networks to the travelling salesman problem
• An inequality with applications to statistical estimation for probabilistic functions of Markov processes and to a model for ecology
• Evolution towards the maximum clique
• Maxima for Graphs and a New Proof of a Theorem of Turán
• On the stability of the travelling salesman problem algorithm of Hopfield and Tank
• Self-organization and associative memory
• The maximum clique problem
• ``Neural computation of decisions in optimization problems

Cited in

(14)

• On the power of neural networks for solving hard problems
• Finding approximate solutions to NP-hard problems by neural networks is hard
• Comparing problem solving strategies for NP-hard optimization problems
• Neural network methods in combinatorial optimization
• Existence and stability of equilibria of the continuous-time Hopfield neural network
• ``Neural computation of decisions in optimization problems
• Finite-time synchronization of coupled Cohen-Grossberg neural networks with and without coupling delays
• Turing computability with neural nets
• scientific article; zbMATH DE number 1886435 (Why is no real title available?)
• scientific article; zbMATH DE number 1886437 (Why is no real title available?)
• scientific article; zbMATH DE number 597347 (Why is no real title available?)
• Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size
• scientific article; zbMATH DE number 1748587 (Why is no real title available?)
• scientific article; zbMATH DE number 4066656 (Why is no real title available?)

Describes a project that uses

Uses Software

• DIMACS

This page was built for publication: Neural networks for NP-complete problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4377229)