Approximate solutions of Happynet on cubic graphs

• Autorzy: Giannakos A. , Pottie O.
• Języki publikacji: EN

Abstrakty

EN

The HAPPYNET problem is defined as follows : Given a undirected simple graph G with integer weights wvu on its edges vu 6 E(G), find a function s : V(G] → { — 1,1} such that ∀νV(G), v is happy in G, i.e. such that . It is easy to see [3] that HAPPYNET has always a solution, no matter what the input is. However, no polynomial algorithm is known for this problem, which is complete for the class PLS (see [4] for a definition). Parberry et al, have shown in [7] that in the case of cubic graphs (i.e. of maximum degree 3) HAPPYNET is as difficult as for arbitrary graphs. A ρ-approximate solution to a HAPPYNET instance of size n can be defined for 0 le ρ le 1 as a natural extension of the solution function, with at least pn happy vertices. In this paper, we present a polynomial-time algorithm that finds a ρ-approximate solution for the HAPPYNET problem on cubic graphs, with ρ 3/4 .

Słowa kluczowe

EN

optimization; approximation; PLS class; Hopfield networks; cubic graphs

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2006
• Tom: Vol. 31, No. 3-4
• Strony: 233--241
• Opis fizyczny: Bibliogr. 7 poz.

Twórcy

autor

Giannakos A.

autor

Pottie O.

• LAMSADE UMR 7024, Universite Paris-Dauphine, Place du Marechal de Lattre de Tasigny, 75775 Paris Cedex 16 France,

Bibliografia

• [1] Godbeer G.H., Lipscomb J., Luby M., On the computational complexity of finding stable state vectors in comiectioriist models (Hopfield nets). Technical Report 208/88: Dept. of Computer Science, Univ. of Toronto, 1988.
• [2] Hopfield J.J., Neural networks and physical systems with emergent collective computational activities, in: Proc. USA Nat. Ac. Sc, 1982, 30, 709-728.
• [3] Papadimitriou C.H.. Computational complexity. Addison-Wesley. 1994.
• [4] Johnson D.S., Papadimitriou C.H.. Yannakakis M.. How easy is local search? in: Proc. 26th FOGS, 1985, 39-42.
• [5] Papadimitriou C.H.. Schaffcr A., Yannakakis M., On the complexity of local search, in: Proc. 22nd STOC, 1990, 439-445.
• [6] Schaffer A., Yannakakis M., Simple local search problems that are hard to solve, SI AM Journal on Computing 20, 1, 1991, 56-87.
• [7] Parberry I., Tseng II.-L., Are Hopfield networks faster than conventional computers? in: Proc. of the 9th Conference on Neural Information Systems, 1997, 238-245.