On the performance guarantee of neural networks for NP-hard optimization problems

DOI10.1016/0020-0190(95)00051-DMaRDI QIDQ672967zbMATH OpenFDO

Authors V. Zissimopoulos

Publication date 28 February 1997

Published in Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

HeuristicsNeural networksCombinatorial optimizationAnalysis of algorithmsApproximation algorithmsCombinatorial problemsMaximum independent setWorst-case analysis

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.) (68W35)

Recommendations

• Finding approximate solutions to NP-hard problems by neural networks is hard
• On the power of neural networks for solving hard problems
• Neural networks for NP-complete problems
• scientific article; zbMATH DE number 558545
• Hardness results for neural network approximation problems

Cites work

• scientific article; zbMATH DE number 41891 (Why is no real title available?)
• A \((\Delta / 2)\)-approximation algorithm for the maximum independent set problem
• Finding approximate solutions to NP-hard problems by neural networks is hard
• On the power of neural networks for solving hard problems

Cited in

(5)

• On the power of neural networks for solving hard problems
• Finding approximate solutions to NP-hard problems by neural networks is hard
• Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size
• Metaheuristics: A bibliography
• scientific article; zbMATH DE number 4066656 (Why is no real title available?)

This page was built for publication: On the performance guarantee of neural networks for NP-hard optimization problems

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