Carsten Peterson
Expert
Neural networks and NP-complete problems; a performance study of the graph bisectioning problem
Författare
Summary, in English
Th e performance of a mean field th eory (MFT) neu ral
network technique for finding approximate solutions to optimi zation
problems is invest igat ed for the case of th e minimum cut graph bisectio
n problem, which is NP- complete. We address the issues of solut ion
quality, programming complexity, convergence tim es and scala bility.
Both standard random gr aphs an d mor e st ruct ured geomet ric graphs
are considered. We find very encouraging res ult s for all t hese aspects
for bisection of graphs with sizes rang ing from 20 to 2000 vertice s. Solution
quality app ear s to be competitive with ot her methods, and the
effort required to apply th e MFT method is minimal . Although th e
MFT neural network approach is inh erently a parallel method , we find
that t he MFT algorithm executes in less tim e than ot her approaches
even when it is simula ted in a serial manner .
network technique for finding approximate solutions to optimi zation
problems is invest igat ed for the case of th e minimum cut graph bisectio
n problem, which is NP- complete. We address the issues of solut ion
quality, programming complexity, convergence tim es and scala bility.
Both standard random gr aphs an d mor e st ruct ured geomet ric graphs
are considered. We find very encouraging res ult s for all t hese aspects
for bisection of graphs with sizes rang ing from 20 to 2000 vertice s. Solution
quality app ear s to be competitive with ot her methods, and the
effort required to apply th e MFT method is minimal . Although th e
MFT neural network approach is inh erently a parallel method , we find
that t he MFT algorithm executes in less tim e than ot her approaches
even when it is simula ted in a serial manner .
Avdelning/ar
- Beräkningsvetenskap för hälsa och miljö
- Centrum för miljö- och klimatvetenskap (CEC)
- Department of Astronomy and Theoretical Physics - Has been reorganised
Publiceringsår
1989
Språk
Engelska
Sidor
59-89
Publikation/Tidskrift/Serie
Complex Systems
Volym
2
Avvikelse
1
Dokumenttyp
Artikel i tidskrift
Ämne
- Bioinformatics (Computational Biology)
Aktiv
Published
Forskningsgrupp
- Computational Science for Health and Environment