Advanced

A Potts Neuron Approach to Communication Routing

Häkkinen, Jari LU ; Lagerholm, Martin; Peterson, Carsten LU and Söderberg, Bo LU (1998) In Neural Computation 10. p.1587-1599
Abstract
A feedback neural network approach to communication routing problems

is developed, with emphasis on Multiple Shortest Path problems,

with several requests for transmissions between distinct start- and

endnodes. The basic ingredients are a set of Potts neurons for each request,with interactions designed to minimize path lengths and to

prevent overloading of network arcs. The topological nature of the

problem is conveniently handled using a propagator matrix approach.

Although the constraints are global, the algorithmic steps are based

entirely on local information, facilitating distributed implementations.

In the polynomially solvable single-request case, the... (More)
A feedback neural network approach to communication routing problems

is developed, with emphasis on Multiple Shortest Path problems,

with several requests for transmissions between distinct start- and

endnodes. The basic ingredients are a set of Potts neurons for each request,with interactions designed to minimize path lengths and to

prevent overloading of network arcs. The topological nature of the

problem is conveniently handled using a propagator matrix approach.

Although the constraints are global, the algorithmic steps are based

entirely on local information, facilitating distributed implementations.

In the polynomially solvable single-request case, the approach reduces

to a fuzzy version of the Bellman-Ford algorithm.

The method is evaluated for synthetic problems of varying sizes and

load levels, by comparing to exact solutions from a branch-and-bound

method, or to approximate solutions from a simple heuristic.

With very few exceptions, the Potts approach gives legal solutions of

very high quality. The computational demand scales merely as the

product of the numbers of requests, nodes, and arcs. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
in
Neural Computation
volume
10
pages
1587 - 1599
publisher
MIT Press
external identifiers
  • Scopus:0142020266
ISSN
1530-888X
DOI
10.1162/089976698300017322
language
English
LU publication?
yes
id
7bd6802b-c9d4-4986-a3f0-6e75fc03eff3 (old id 1543946)
date added to LUP
2010-02-25 15:05:00
date last changed
2016-04-16 11:20:31
@misc{7bd6802b-c9d4-4986-a3f0-6e75fc03eff3,
  abstract     = {A feedback neural network approach to communication routing problems<br/><br>
is developed, with emphasis on Multiple Shortest Path problems,<br/><br>
with several requests for transmissions between distinct start- and<br/><br>
endnodes. The basic ingredients are a set of Potts neurons for each request,with interactions designed to minimize path lengths and to <br/><br>
prevent overloading of network arcs. The topological nature of the <br/><br>
problem is conveniently handled using a propagator matrix approach. <br/><br>
Although the constraints are global, the algorithmic steps are based <br/><br>
entirely on local information, facilitating distributed implementations.<br/><br>
In the polynomially solvable single-request case, the approach reduces<br/><br>
to a fuzzy version of the Bellman-Ford algorithm.<br/><br>
The method is evaluated for synthetic problems of varying sizes and<br/><br>
load levels, by comparing to exact solutions from a branch-and-bound<br/><br>
method, or to approximate solutions from a simple heuristic.<br/><br>
With very few exceptions, the Potts approach gives legal solutions of<br/><br>
very high quality. The computational demand scales merely as the<br/><br>
product of the numbers of requests, nodes, and arcs.},
  author       = {Häkkinen, Jari and Lagerholm, Martin and Peterson, Carsten and Söderberg, Bo},
  issn         = {1530-888X},
  language     = {eng},
  pages        = {1587--1599},
  publisher    = {ARRAY(0xafd04c8)},
  series       = {Neural Computation},
  title        = {A Potts Neuron Approach to Communication Routing},
  url          = {http://dx.doi.org/10.1162/089976698300017322},
  volume       = {10},
  year         = {1998},
}