A neural algorithm for solving approximately the maximum 2-satisfiability problem is presented and its performance is analysed: the worst case relative error is 0.25 and the computation time is bounded by nm/4, where n is the number of variables and m the number of clauses of a problem instance. Simulation experiments show a very good average case performance. We design a uniform family of circuits of small size and depth to implement the algorithm and present an efficient realization on field programmable gate arrays.

A neural algorithm for MAX-2SAT: Performance analysis and circuit implementation / M.A. Alberti, A. Bertoni, P. Campadelli, G. Grossi, R. Posenato. - In: NEURAL NETWORKS. - ISSN 0893-6080. - 10:3(1997), pp. 555-560. [10.1016/S0893-6080(96)00065-2]

A neural algorithm for MAX-2SAT: Performance analysis and circuit implementation

M.A. Alberti;A. Bertoni;P. Campadelli;G. Grossi;
1997

Abstract

A neural algorithm for solving approximately the maximum 2-satisfiability problem is presented and its performance is analysed: the worst case relative error is 0.25 and the computation time is bounded by nm/4, where n is the number of variables and m the number of clauses of a problem instance. Simulation experiments show a very good average case performance. We design a uniform family of circuits of small size and depth to implement the algorithm and present an efficient realization on field programmable gate arrays.
approximation; Hopfield networks; optimization; programmable gate arrays; satisfiability
Settore INF/01 - Informatica
Article (author)
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2434/937929
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 15
  • ???jsp.display-item.citation.isi??? 7
social impact