๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Neural networks for NP-complete problems

โœ Scribed by Marco Budinich

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
547 KB
Volume
30
Category
Article
ISSN
0362-546X

No coin nor oath required. For personal study only.

โœฆ Synopsis

combinatorial optimization is an active field of research in Neural Networks. Since the first attempts to solve the travelling salesman problem with Hopfield nets several progresses have been made. I will present some Neural Network approximate solutions for NP-complete problems that have a sound mathematical foundation and that, beside their theoretical interest, are also numerically encouraging. These algorithms easily deal with problems with thousands of instances taking Neural Network approaches out of the "toy-problem" era.

๐Ÿ“œ SIMILAR VOLUMES

Complete problems for monotone NP
Complete problems for monotone NP
โœ Iain A. Stewart ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 768 KB
Training a 3-node neural network is NP-c
Training a 3-node neural network is NP-complete
โœ Avrim L. Blum; Ronald L. Rivest ๐Ÿ“‚ Article ๐Ÿ“… 1992 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 956 KB

We consider a 2-layer, 3-node, n-input neural network whose nodes compute linear threshold functions of their inputs. We show that it is NP-complete to decide whether there exist weights and thresholds for this network so that it produces output consistent with a given set of training examples. We e

NP-complete scheduling problems
NP-complete scheduling problems
โœ J.D. Ullman ๐Ÿ“‚ Article ๐Ÿ“… 1975 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 423 KB

We show that the problem of finding an optimal schedule for a set of jobs is NPcomplete even in the following two restricted cases. (1) All jobs require one time unit. (2) All jobs require one or two time units, and there are only two processor resolving (in the negative a conjecture of R. L. Grah

On the np-completeness of certain networ
On the np-completeness of certain network testing problems
โœ S. Even; O. Goldreich; S. Moran; P. Tong ๐Ÿ“‚ Article ๐Ÿ“… 1984 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 946 KB

Let G ( V , E) be an undirected graph which describes the structure of a communication network. During the maintenance period every line must be tested in each of the two possible directions. A line is tested by assigning one of its endpoints t o be a transmitter, the other to be a receiver, and sen