hig.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard-cite-them-right
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • sv-SE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • de-DE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A Slime Mold Solver for Linear Programming Problems
University of Gävle, Faculty of Engineering and Sustainable Development, Department of Electronics, Mathematics and Natural Sciences, Mathematics. (Matematik)
School of Engineering and Applied Sciences, Harvard University.
2012 (English)In: How the World Computes: Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012, Cambridge, UK, June 18-23, 2012. Proceedings / [ed] S. Barry Cooper , Anuj Dawar and Benedikt Löwe, Springer, 2012, p. 344-354Conference paper, Published paper (Refereed)
Abstract [en]

Physarum polycephalum (true slime mold) has recently emerged as a fascinating example of biological computation through morphogenesis. Despite being a single cell organism, experiments have observed that through its growth process, the Physarum is able to solve various minimum cost flow problems. This paper analyzes a mathematical model of the Physarum growth dynamics. We show how to encode general linear programming (LP) problems as instances of the Physarum. We prove that under the growth dynamics, the Physarum is guaranteed to converge to the optimal solution of the LP. We further derive an efficient discrete algorithm based on the Physarum model, and experimentally verify its performance on assignment problems.

Place, publisher, year, edition, pages
Springer, 2012. p. 344-354
Series
Lecture notes in Computer Science, ISSN 0302-9743 ; 7318
Keywords [en]
Physarum, Linear programming
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:hig:diva-12929DOI: 10.1007/978-3-642-30870-3_35ISBN: 978-3-642-30869-7 (print)OAI: oai:DiVA.org:hig-12929DiVA, id: diva2:553020
Conference
Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012, Cambridge, UK, June 18-23, 2012
Available from: 2012-09-17 Created: 2012-09-17 Last updated: 2018-03-13Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records BETA

Johansson, Anders

Search in DiVA

By author/editor
Johansson, Anders
By organisation
Mathematics
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 82 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard-cite-them-right
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • sv-SE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • de-DE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf