12 citations · 42 across the 21 of their papers we have counts for
7 papers · 1 filter
Physarum-Inspired Multi-Commodity Flow Dynamics
Vincenzo Bonifaci, Enrico Facca, Frederic Folz +6
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 pr…
Secretary and Online Matching Problems with Machine Learned Advice
Antonios Antoniadis, Themis Gouleakis, Pieter Kleer +1
The classical analysis of online algorithms, due to its worst-case nature, can be quite pessimistic when the input instance at hand is far from worst-case. Often this is not an iss…
Convergence of the Non-Uniform Physarum Dynamics
Andreas Karrenbauer, Pavel Kolev, Kurt Mehlhorn
Let , , and . We show under fairly general conditions that the non-uniform Physarum dynamics \[ \dot{x}_…
A PTAS for -Low Rank Approximation
Frank Ban, Vijay Bhattiprolu, Karl Bringmann +3
A number of recent works have studied algorithms for entrywise -low rank approximation, namely, algorithms which given an matrix (with ), output…
Approximation Algorithms for -Low Rank Approximation
Karl Bringmann, Pavel Kolev, David P. Woodruff
We study the -Low Rank Approximation Problem, where the goal is, given an matrix , to output a rank- matrix for which is minimized. Her…
Two Results on Slime Mold Computations
Ruben Becker, Vincenzo Bonifaci, Andreas Karrenbauer +2
We present two results on slime mold computations. In wet-lab experiments (Nature'00) by Nakagaki et al. the slime mold Physarum polycephalum demonstrated its ability to solve shor…
Density Independent Algorithms for Sparsifying -Step Random Walks
Gorav Jindal, Pavel Kolev, Richard Peng +1
We give faster algorithms for producing sparse approximations of the transition matrices of -step random walks on undirected, weighted graphs. These transition matrices also for…