Finding approximate solutions to NP-hard problems by neural networks is hard

DOI10.1016/0020-0190(92)90261-SzbMath0743.68082OpenAlexW2068321983MaRDI QIDQ1186583

Xin Yao

Publication date: 28 June 1992

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

Full work available at URL: https://doi.org/10.1016/0020-0190(92)90261-s

zbMATH Keywords

approximate solutionsneural networkshard combinatorial optimization problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Combinatorial optimization (90C27) Traffic problems in operations research (90B20)

Related Items

A primer on the application of neural networks to covering array generation, Design rules for application specific dynamical systems, A neural network system for solving an assortment problem in the steel industry, Metaheuristics: A bibliography, Heuristics from Nature for Hard Combinatorial Optimization Problems, On the performance guarantee of neural networks for NP-hard optimization problems, Neural networks as systems for recognizing patterns, A neural network for the minimum set covering problem

Cites Work

• Unnamed Item
• Unnamed Item
• On the power of neural networks for solving hard problems
• ``Neural computation of decisions in optimization problems
• On Approximate Solutions for Combinatorial Optimization Problems
• The Complexity of Near-Optimal Graph Coloring
• Neural networks and physical systems with emergent collective computational abilities.