Aneuralalgorithm 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 , 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
POSENATO, Roberto
1997-01-01
Abstract
Aneuralalgorithm 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 , 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.
File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
posenatoNNS0893-60809600065-2.pdf
solo utenti autorizzati
Descrizione: post-print
Tipologia:
Documento in Post-print
Licenza:
Accesso ristretto
Dimensione
1.19 MB
Formato
Adobe PDF
|
1.19 MB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
