The directed Physarum dynamics is known to solve positive linear programs: minimize @math subject to @math and @math for a positive cost vector @math . The directed Physarum dynamics evolves a positive vector @math according to the dynamics @math . Here @math is the solution to @math that minimizes the "energy" @math . In this paper, we study the non-uniform directed dynamics @math , where @math is a positive diagonal matrix. The non-uniform dynamics is more complex than the uniform dynamics (with @math being the identity matrix), as it allows each component of @math to react with different speed to the differences between @math and @math . Our contribution is to show that the non-uniform directed dynamics solves positive linear programs.
The paper @cite_11 proposes a mathematical model for the behavior of the slime and argues extensively that the model is adequate. Physarum is modeled as an electrical network with time varying resistors. We have a simple graph @math with two distinguished nodes modeling the food sources. Each edge @math has a positive length @math and a positive capacity @math ; @math is fixed, but @math is a function of time. The resistance @math of @math is @math . In the electrical network defined by these resistances, a current of value 1 is forced from one of the distinguished nodes to the other. For an (arbitrarily oriented) edge @math , let @math be the resulting current over @math . Then, the capacity of @math evolves according to the differential equation where @math is the derivative of @math with respect to time.
@cite_11
2003810228
We study undirected networks with edge costs that satisfy the triangle inequality. Let @math denote the number of nodes. We present an @math -approximation algorithm for a generalization of the metric-cost subset @math -node-connectivity problem. Our approximation guarantee is proved via lower bounds that apply to the simple edge-connectivity version of the problem, where the requirements are for edge-disjoint paths rather than for openly node-disjoint paths. A corollary is that, for metric costs and for each @math , there exists a @math -node connected graph whose cost is within a factor of @math of the cost of any simple @math -edge connected graph. Based on our @math -approximation algorithm, we present an @math -approximation algorithm for the metric-cost node-connectivity survivable network design problem, where @math denotes the maximum requirement over all pairs of nodes. Our results contrast with the case of edge costs of 0 or 1, where Kortsarz, Krauthgamer, and Lee. [SIAM J. Comput., 33 (2004), pp. 704-720] recently proved, assuming NP @math DTIME( @math ), a hardness-of-approximation lower bound of @math for the subset @math -node-connectivity problem, where @math denotes a small positive number.