In wet-lab experiments, the slime mold Physarum polycephalum has demonstrated its ability to solve shortest path problems and to design efficient networks. For the shortest path problem, a mathematical model for the evolution of the slime is availabl
e and it has been shown in computer experiments and through mathematical analysis that the dynamics solves the shortest path problem. In this paper, we introduce a dynamics for the network design problem. We formulate network design as the problem of constructing a network that efficiently supports a multi-commodity flow problem. We investigate the dynamics in computer simulations and analytically. The simulations show that the dynamics is able to construct efficient and elegant networks. In the theoretical part we show that the dynamics minimizes an objective combining the cost of the network and the cost of routing the demands through the network. We also give alternative characterization of the optimum solution.
We propose a novel differentiable reformulation of the linearly-constrained $ell_1$ minimization problem, also known as the basis pursuit problem. The reformulation is inspired by the Laplacian paradigm of network theory and leads to a new family of
gradient-based methods for the solution of $ell_1$ minimization problems. We analyze the iteration complexity of a natural solution approach to the reformulation, based on a multiplicative weights update scheme, as well as the iteration complexity of an accelerated gradient scheme. The results can be seen as bounds on the complexity of iteratively reweighted least squares (IRLS) type methods of basis pursuit.
The computation of electrical flows is a crucial primitive for many recently proposed optimization algorithms on weighted networks. While typically implemented as a centralized subroutine, the ability to perform this task in a fully decentralized way
is implicit in a number of biological systems. Thus, a natural question is whether this task can provably be accomplished in an efficient way by a network of agents executing a simple protocol. We provide a positive answer, proposing two distributed approaches to electrical flow computation on a weighted network: a deterministic process mimicking Jacobis iterative method for solving linear systems, and a randomized token diffusion process, based on revisiting a classical random walk process on a graph with an absorbing node. We show that both processes converge to a solution of Kirchhoffs node potential equations, derive bounds on their convergence rates in terms of the weights of the network, and analyze their time and message complexity.
We present two results on slime mold computations. In wet-lab experiments (Nature00) by Nakagaki et al. the slime mold Physarum polycephalum demonstrated its ability to solve shortest path problems. Biologists proposed a mathematical model, a system
of differential equations, for the slimes adaption process (J. Theoretical Biology07). It was shown that the process convergences to the shortest path (J. Theoretical Biology12) for all graphs. We show that the dynamics actually converges for a much wider class of problems, namely undirected linear programs with a non-negative cost vector. Combinatorial optimization researchers took the dynamics describing slime behavior as an inspiration for an optimization method and showed that its discretization can $varepsilon$-approximately solve linear programs with positive cost vector (ITCS16). Their analysis requires a feasible starting point, a step size depending linearly on $varepsilon$, and a number of steps with quartic dependence on $mathrm{opt}/(varepsilonPhi)$, where $Phi$ is the difference between the smallest cost of a non-optimal basic feasible solution and the optimal cost ($mathrm{opt}$). We give a refined analysis showing that the dynamics initialized with any strongly dominating point converges to the set of optimal solutions. Moreover, we strengthen the convergence rate bounds and prove that the step size is independent of $varepsilon$, and the number of steps depends logarithmically on $1/varepsilon$ and quadratically on $mathrm{opt}/Phi$.
We consider a system of nonlinear ordinary differential equations for the solution of linear programming (LP) problems that was first proposed in the mathematical biology literature as a model for the foraging behavior of acellular slime mold Physaru
m polycephalum, and more recently considered as a method to solve LPs. We study the convergence time of the continuous Physarum dynamics in the context of the linear programming problem, and derive a new time bound to approximate optimality that depends on the relative entropy between project
Optimization of fluid transport in the slime mold Physarum polycephalum has been the subject of several modeling efforts in recent literature. Existing models assume that the tube adaptation mechanism in P. polycephalums tubular network is controlled
by the sheer amount of fluid flow through the tubes. We put forward the hypothesis that the controlling variable may instead be the flows pressure gradient along the tube. We carry out the stability analysis of such a revised mathematical model for a parallel-edge network, proving that the revised model supports the global flow-optimizing behavior of the slime mold for a substantially wider class of response functions compared to previous models. Simulations also suggest that the same conclusion may be valid for arbitrary network topologies.
A model has been proposed in [Baruah et al., in Proceedings of the IEEE Real-Time Systems Symposium 2012] for representing recurrent precedence-constrained tasks to be executed on multiprocessor platforms, where each recurrent task is modeled by a di
rected acyclic graph (DAG), a period, and a relative deadline. Each vertex of the DAG represents a sequential job, while the edges of the DAG represent precedence constraints between these jobs. All the jobs of the DAG are released simultaneously and have to be completed within some specified relative deadline. The task may release jobs in this manner an unbounded number of times, with successive releases occurring at least the specified period apart. The feasibility problem is to determine whether such a recurrent task can be scheduled to always meet all deadlines on a specified number of dedicated processors. The case of a single task has been considered in [Baruah et al., 2012]. The main contribution of this paper is to consider the case of multiple tasks. We show that EDF has a speedup bound of 2-1/m, where m is the number of processors. Moreover, we present polynomial and pseudopolynomial schedulability tests, of differing effectiveness, for determining whether a set of sporadic DAG tasks can be scheduled by EDF to meet all deadlines on a specified number of processors.
Physarum Polycephalum is a slime mold that is apparently able to solve shortest path problems. A mathematical model has been proposed by biologists to describe the feedback mechanism used by the slime mold to adapt its tubular channels while foragi
ng two food sources s0 and s1. We prove that, under this model, the mass of the mold will eventually converge to the shortest s0 - s1 path of the network that the mold lies on, independently of the structure of the network or of the initial mass distribution. This matches the experimental observations by the biologists and can be seen as an example of a natural algorithm, that is, an algorithm developed by evolution over millions of years.
We give the first algorithm for testing the feasibility of a system of sporadic real-time tasks on a set of identical processors, solving one major open problem in the area of multiprocessor real-time scheduling [S.K. Baruah and K. Pruhs, Journal of
Scheduling, 2009]. We also investigate the related notion of schedulability and a notion that we call online feasibility. Finally, we show that discrete-time schedules are as powerful as continuous-time schedules, which answers another open question in the above mentioned survey.
