0
$\begingroup$

I have been recently researching Happynet in terms of approximation and I have found out that there is a little interest in this topic.

What's the reason for this? Are there any related problems, that get better attention?

The Happynet problem is related to minimizing the energy in a Hopfield net.

The problem is defined as follows: Given a graph $G = (V,E)$ and edge weights $w: E \to \mathbb{Z}$, find a function $s: V \to \{-1,1\}$ such that for all $v \in V$, the sum $$\sum_{u: \{v,u\} \in E} s(v)s(u)w(\{u,v\})$$ is non-negative.

Put otherwise, the task is to find a cut in an edge-weighted graph $G$ such that for each node $v$ the total weight of cut-edges incident to $v$ is at most as large as the total weight of non-cut-edges incident to $v$.

Curiously, a feasible solution always exists. However, it seems that no polynomial-time algorithm is known for solving the problem. For more information, see e.g. Giannakos and Pottie (2005).

Improve this question
$\endgroup$
4
  • $\begingroup$ Are you talking about minimizing the energy function of Hopfield nets? en.wikipedia.org/wiki/Hopfield_net $\endgroup$ – Hartmut Klauck Mar 12 '11 at 14:12
  • 6
    $\begingroup$ Yes, this question needs more detail/context $\endgroup$ – Suresh Venkat Mar 12 '11 at 16:49
  • $\begingroup$ I don't really know that much about the field, but to me it seems like the Happynet problem ("stable configuration") and its variants have been studied a lot from the perspective of PLS-completeness. Googling for "max-cut" and "PLS" might be helpful; note that the local search variant of weighted max-cut (flip-neighbourhoods) is essentially the same problem as Happynet restricted to negative edge weights. $\endgroup$ – Jukka Suomela Mar 13 '11 at 13:27
  • $\begingroup$ -1 What's the point of this question? $\endgroup$ – Oleksandr Bondarenko Mar 17 '11 at 15:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.