Source author record

Pavel Kolev

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Complexity Discrete Mathematics Machine Learning math.DS math.OC Neural and Evolutionary Computing

Catalog footprint

Research overview

5works

7topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Physarum-Inspired Multi-Commodity Flow Dynamics

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 available 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.

preprint2021arXiv

A PTAS for $\ell_p$ -Low Rank Approximation

A number of recent works have studied algorithms for entrywise $\ell_p$ -low rank approximation, namely, algorithms which given an $n \times d$ matrix $A$ (with $n \geq d$ ), output a rank- $k$ matrix $B$ minimizing $\|A-B\|_p^p=\sum_{i,j}|A_{i,j}-B_{i,j}|^p$ when $p > 0$ ; and $\|A-B\|_0=\sum_{i,j}[A_{i,j}\neq B_{i,j}]$ for $p=0$ . On the algorithmic side, for $p \in (0,2)$ , we give the first $(1+ε)$ -approximation algorithm running in time $n^{\text{poly}(k/ε)}$ . Further, for $p = 0$ , we give the first almost-linear time approximation scheme for what we call the Generalized Binary $\ell_0$ -Rank- $k$ problem. Our algorithm computes $(1+ε)$ -approximation in time $(1/ε)^{2^{O(k)}/ε^{2}} \cdot nd^{1+o(1)}$ . On the hardness of approximation side, for $p \in (1,2)$ , assuming the Small Set Expansion Hypothesis and the Exponential Time Hypothesis (ETH), we show that there exists $δ:= δ(α) > 0$ such that the entrywise $\ell_p$ -Rank- $k$ problem has no $α$ -approximation algorithm running in time $2^{k^δ}$ .

preprint2020arXiv

Convergence of the Non-Uniform Directed Physarum Model

The directed Physarum dynamics is known to solve positive linear programs: minimize $c^T x$ subject to $Ax = b$ and $x \ge 0$ for a positive cost vector $c$ . The directed Physarum dynamics evolves a positive vector $x$ according to the dynamics $\dot{x} = q(x) - x$ . Here $q(x)$ is the solution to $Af = b$ that minimizes the "energy" $\sum_i c_i f_i^2/x_i$ . In this paper, we study the non-uniform directed dynamics $\dot{x} = D(q(x) - x)$ , where $D$ is a positive diagonal matrix. The non-uniform dynamics is more complex than the uniform dynamics (with $D$ being the identity matrix), as it allows each component of $x$ to react with different speed to the differences between $q(x)$ and $x$ . Our contribution is to show that the non-uniform directed dynamics solves positive linear programs.

preprint2020arXiv

Convergence of the Non-Uniform Physarum Dynamics

Let $c \in \mathbb{Z}^m_{> 0}$ , $A \in \mathbb{Z}^{n\times m}$ , and $b \in \mathbb{Z}^n$ . We show under fairly general conditions that the non-uniform Physarum dynamics $\dot{x}_e = a_e(x,t) \left(|q_e| - x_e\right)$ converges to the optimum solution $x^*$ of the weighted basis pursuit problem minimize $c^T x$ subject to $A f = b$ and $|f| \le x$ . Here, $f$ and $x$ are $m$ -vectors of real variables, $q$ minimizes the energy $\sum_e (c_e/x_e) q_e^2$ subject to the constraints $A q = b$ and $\mathrm{supp}(q) \subseteq \mathrm{supp}(x)$ , and $a_e(x,t) > 0$ is the reactivity of edge $e$ to the difference $|q_e| - x_e$ at time $t$ and in state $x$ . Previously convergence was only shown for the uniform case $a_e(x,t) = 1$ for all $e$ , $x$ , and $t$ . We also show convergence for the dynamics $\dot{x}_e = x_e \cdot \left( g_e \left(\frac{|q_e|}{x_e}\right) - 1\right),$ where $g_e$ is an increasing differentiable function with $g_e(1) = 1$ . Previously convergence was only shown for the special case of the shortest path problem on a graph consisting of two nodes connected by parallel edges.

preprint2016arXiv

An Efficient Parallel Algorithm for Spectral Sparsification of Laplacian and SDDM Matrix Polynomials

For "large" class $\mathcal{C}$ of continuous probability density functions (p.d.f.), we demonstrate that for every $w\in\mathcal{C}$ there is mixture of discrete Binomial distributions (MDBD) with $T\geq N\sqrt{ϕ_{w}/δ}$ distinct Binomial distributions $B(\cdot,N)$ that $δ$ -approximates a discretized p.d.f. $\widehat{w}(i/N)\triangleq w(i/N)/[\sum_{\ell=0}^{N}w(\ell/N)]$ for all $i\in[3:N-3]$ , where $ϕ_{w}\geq\max_{x\in[0,1]}|w(x)|$ . Also, we give two efficient parallel algorithms to find such MDBD. Moreover, we propose a sequential algorithm that on input MDBD with $N=2^k$ for $k\in\mathbb{N}_{+}$ that induces a discretized p.d.f. $β$ , $B=D-M$ that is either Laplacian or SDDM matrix and parameter $ε\in(0,1)$ , outputs in $\widehat{O}(ε^{-2}m + ε^{-4}nT)$ time a spectral sparsifier $D-\widehat{M}_{N} \approx_ε D-D\sum_{i=0}^{N}β_{i}(D^{-1} M)^i$ of a matrix-polynomial, where $\widehat{O}(\cdot)$ notation hides $\mathrm{poly}(\log n,\log N)$ factors. This improves the Cheng et al.'s [CCLPT15] algorithm whose run time is $\widehat{O}(ε^{-2} m N^2 + NT)$ . Furthermore, our algorithm is parallelizable and runs in work $\widehat{O}(ε^{-2}m + ε^{-4}nT)$ and depth $O(\log N\cdot\mathrm{poly}(\log n)+\log T)$ . Our main algorithmic contribution is to propose the first efficient parallel algorithm that on input continuous p.d.f. $w\in\mathcal{C}$ , matrix $B=D-M$ as above, outputs a spectral sparsifier of matrix-polynomial whose coefficients approximate component-wise the discretized p.d.f. $\widehat{w}$ . Our results yield the first efficient and parallel algorithm that runs in nearly linear work and poly-logarithmic depth and analyzes the long term behaviour of Markov chains in non-trivial settings. In addition, we strengthen the Spielman and Peng's [PS14] parallel SDD solver.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Pavel Kolev

Research overview

Is this your work?

5 publications

Physarum-Inspired Multi-Commodity Flow Dynamics

A PTAS for $\ell_p$ -Low Rank Approximation

Convergence of the Non-Uniform Directed Physarum Model

Convergence of the Non-Uniform Physarum Dynamics

An Efficient Parallel Algorithm for Spectral Sparsification of Laplacian and SDDM Matrix Polynomials

See the researcher in context

Building this map preview

Pavel Kolev

Research overview

Is this your work?

5 publications

Physarum-Inspired Multi-Commodity Flow Dynamics

A PTAS for ℓp\ell_pℓp​-Low Rank Approximation

Convergence of the Non-Uniform Directed Physarum Model

Convergence of the Non-Uniform Physarum Dynamics

An Efficient Parallel Algorithm for Spectral Sparsification of Laplacian and SDDM Matrix Polynomials

See the researcher in context

Building this map preview

A PTAS for $\ell_p$ -Low Rank Approximation