Zobrazeno 1 - 10
of 293
pro vyhledávání: '"Czumaj, Artur"'
We consider two natural variants of the problem of minimum spanning tree (MST) of a graph in the parallel setting: MST verification (verifying if a given tree is an MST) and the sensitivity analysis of an MST (finding the lowest cost replacement edge
Externí odkaz:
http://arxiv.org/abs/2408.00398
We design new parallel algorithms for clustering in high-dimensional Euclidean spaces. These algorithms run in the Massively Parallel Computation (MPC) model, and are fully scalable, meaning that the local memory in each machine may be $n^{\sigma}$ f
Externí odkaz:
http://arxiv.org/abs/2307.07848
We consider the distributed complexity of the (degree+1)-list coloring problem, in which each node $u$ of degree $d(u)$ is assigned a palette of $d(u)+1$ colors, and the goal is to find a proper coloring using these color palettes. The (degree+1)-lis
Externí odkaz:
http://arxiv.org/abs/2306.12071
We consider the classic $k$-center problem in a parallel setting, on the low-local-space Massively Parallel Computation (MPC) model, with local space per machine of $\mathcal{O}(n^{\delta})$, where $\delta \in (0,1)$ is an arbitrary constant. As a ce
Externí odkaz:
http://arxiv.org/abs/2304.05883
Graph coloring problems are among the most fundamental problems in parallel and distributed computing, and have been studied extensively in both settings. In this context, designing efficient deterministic algorithms for these problems has been found
Externí odkaz:
http://arxiv.org/abs/2302.04378
We consider the problem of computing routing schemes in the $\mathsf{HYBRID}$ model of distributed computing where nodes have access to two fundamentally different communication modes. In this problem nodes have to compute small labels and routing ta
Externí odkaz:
http://arxiv.org/abs/2210.05333
Autor:
Czumaj, Artur, Filtser, Arnold, Jiang, Shaofeng H. -C., Krauthgamer, Robert, Veselý, Pavel, Yang, Mingwei
In Euclidean Uniform Facility Location (UFL), the input is a set of clients in $\mathbb{R}^d$ and the goal is to place facilities to serve them, so as to minimize the total cost of opening facilities plus connecting the clients. We study the setting
Externí odkaz:
http://arxiv.org/abs/2204.02095
Autor:
Coy, Sam, Czumaj, Artur, Feldmann, Michael, Hinnenthal, Kristian, Kuhn, Fabian, Scheideler, Christian, Schneider, Philipp, Struijs, Martijn
Hybrid networks, i.e., networks that leverage different means of communication, become ever more widespread. To allow theoretical study of such networks, [Augustine et al., SODA'20] introduced the $\mathsf{HYBRID}$ model, which is based on the concep
Externí odkaz:
http://arxiv.org/abs/2202.08008
We present a deterministic $O(\log \log \log n)$-round low-space Massively Parallel Computation (MPC) algorithm for the classical problem of $(\Delta+1)$-coloring on $n$-vertex graphs. In this model, every machine has a sublinear local memory of size
Externí odkaz:
http://arxiv.org/abs/2112.05831
Autor:
Czumaj, Artur, Lingas, Andrzej
The {\em parallel time} of a population protocol is defined as the average number of required interactions that an agent in the protocol participates, i.e., the quotient between the total number of interactions required by the protocol and the total
Externí odkaz:
http://arxiv.org/abs/2108.11613