Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Neural networks and NP-complete problems; a performance study of the graph bisectioning problem

Peterson, Carsten LU and Anderson, James R (1989) In Complex Systems 2(1). p.59-89
Abstract
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... (More)
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 . (Less)
Please use this url to cite or link to this publication:
author
and
organization
publishing date
type
Contribution to journal
publication status
published
subject
in
Complex Systems
volume
2
issue
1
pages
10 pages
language
English
LU publication?
yes
id
863930c7-91a5-45dd-8be6-d9a7c5de0a96
alternative location
https://www.complex-systems.com/issues/02-1/
date added to LUP
2024-12-10 10:08:44
date last changed
2025-06-12 13:24:20
@article{863930c7-91a5-45dd-8be6-d9a7c5de0a96,
  abstract     = {{Th e performance of a mean field th eory (MFT) neu ral<br/>network technique for finding approximate solutions to optimi zation<br/>problems is invest igat ed for the case of th e minimum cut graph bisectio<br/>n problem, which is NP- complete. We address the issues of solut ion<br/>quality, programming complexity, convergence tim es and scala bility.<br/>Both standard random gr aphs an d mor e st ruct ured geomet ric graphs<br/>are considered. We find very encouraging res ult s for all t hese aspects<br/>for bisection of graphs with sizes rang ing from 20 to 2000 vertice s. Solution<br/>quality app ear s to be competitive with ot her methods, and the<br/>effort required to apply th e MFT method is minimal . Although th e<br/>MFT neural network approach is inh erently a parallel method , we find<br/>that t he MFT algorithm executes in less tim e than ot her approaches<br/>even when it is simula ted in a serial manner .}},
  author       = {{Peterson, Carsten and Anderson, James R}},
  language     = {{eng}},
  number       = {{1}},
  pages        = {{59--89}},
  series       = {{Complex Systems}},
  title        = {{Neural networks and NP-complete problems; a performance study of the graph bisectioning problem}},
  url          = {{https://www.complex-systems.com/issues/02-1/}},
  volume       = {{2}},
  year         = {{1989}},
}