English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
  Local TagsRelease HistoryDetailsSummary

Released
Paper

Physarum Inspired Dynamics to Solve Semi-Definite Programs

MPS-Authors
/persons/resource/persons284886

Gao,  Yuan
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons44737

Karrenbauer,  Andreas       
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45021

Mehlhorn,  Kurt       
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

2111.02291.pdf
(Preprint), 318KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Gao, Y., Kamkari, H., Karrenbauer, A., Mehlhorn, K., & Sharifi, M. (2022). Physarum Inspired Dynamics to Solve Semi-Definite Programs. Retrieved from https://arxiv.org/abs/2111.02291.


Cite as: https://hdl.handle.net/21.11116/0000-0009-B656-9
Abstract
Physarum Polycephalum is a Slime mold that can solve the shortest path
problem. A mathematical model based on the Physarum's behavior, known as the
Physarum Directed Dynamics, can solve positive linear programs. In this paper,
we will propose a Physarum based dynamic based on the previous work and
introduce a new way to solve positive Semi-Definite Programming (SDP) problems,
which are more general than positive linear programs. Empirical results suggest
that this extension of the dynamic can solve the positive SDP showing that the
nature-inspired algorithm can solve one of the hardest problems in the
polynomial domain. In this work, we will formulate an accurate algorithm to
solve positive and some non-negative SDPs and formally prove some key
characteristics of this solver thus inspiring future work to try and refine
this method.