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

DOI10.1016/0020-0190(95)00051-DzbMATH Open0875.68552MaRDI QIDQ672967FDOQ672967

Authors: V. Zissimopoulos 

Publication date: 28 February 1997

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

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

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)

Cites Work

• Title not available (Why is that?)
• 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
• Title not available (Why is that?)

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)