Next: MAXIMUM CHANNEL ASSIGNMENT
Up: Miscellaneous
Previous: MAXIMUM STRING FOLDING
  Index
- INSTANCE:
An n-node synchronous binary Hopfield network and a stable initial vector
of states
.
A binary Hopfield network is a complete graph where each
edge has an integer weight w(vi,vj) and each vertex has an integer
threshold value t(vi). At each time step t each vertex vi has a state
x(t,vi). x(0,vi) is given by u and
where
is the sign function. An initial vector
of states is stable if x(t,vi) eventually converges for all i.
- SOLUTION:
An initial vector of states v that either converges to a different vector
than u or is not stable.
- MEASURE:
The Hamming distance between u and v.
If v is the vector nearest to u that does not converge to the same vector
as u, then this distance is the attraction radius.
- Bad News:
Not approximable within
for any
[154].
- Comment:
Transformation from MINIMUM INDEPENDENT DOMINATING SET.
Next: MAXIMUM CHANNEL ASSIGNMENT
Up: Miscellaneous
Previous: MAXIMUM STRING FOLDING
  Index
Viggo Kann
1999-04-22