23 citations · 60 across the 19 of their papers we have counts for
14 papers · 1 filter
Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances
Václav Rozhoň, Bernhard Haeupler, Anders Martinsson +2
We introduce stronger notions for approximate single-source shortest-path distances, show how to efficiently compute them from weaker standard notions, and demonstrate the algorith…
A Simple Deterministic Distributed Low-Diameter Clustering
Václav Rozhoň, Bernhard Haeupler, Christoph Grunau
We give a simple, local process for nodes in an undirected graph to form non-adjacent clusters that (1) have at most a polylogarithmic diameter and (2) contain at least half of all…
Improved Distributed Network Decomposition, Hitting Sets, and Spanners, via Derandomization
Mohsen Ghaffari, Christoph Grunau, Bernhard Haeupler +2
This paper presents significantly improved deterministic algorithms for some of the key problems in the area of distributed graph algorithms, including network decomposition, hitti…
Local Distributed Rounding: Generalized to MIS, Matching, Set Cover, and Beyond
Salwa Faour, Mohsen Ghaffari, Christoph Grunau +2
We develop a general deterministic distributed method for locally rounding fractional solutions of graph problems for which the analysis can be broken down into analyzing pairs of…
A Nearly Tight Analysis of Greedy k-means++
Christoph Grunau, Ahmet Alper Özüdoğru, Václav Rozhoň +1
The famous -means++ algorithm of Arthur and Vassilvitskii [SODA 2007] is the most popular way of solving the -means problem in practice. The algorithm is very simple: it samp…
Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity Certificates
Marcel Bezdrighin, Michael Elkin, Mohsen Ghaffari +4
This paper presents efficient distributed algorithms for a number of fundamental problems in the area of graph sparsification: We provide the first deterministic distributed algori…
Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and Parallel Applications
Václav Rozhoň, Michael Elkin, Christoph Grunau +1
This paper presents new deterministic and distributed low-diameter decomposition algorithms for weighted graphs. In particular, we show that if one can efficiently compute approxim…
The randomized local computation complexity of the Lovász local lemma
Sebastian Brandt, Christoph Grunau, Václav Rozhoň
The Local Computation Algorithm (LCA) model is a popular model in the field of sublinear-time algorithms that measures the complexity of an algorithm by the number of probes the al…
Improved Deterministic Network Decomposition
Mohsen Ghaffari, Christoph Grunau, Václav Rozhoň
Network decomposition is a central tool in distributed graph algorithms. We present two improvements on the state of the art for network decomposition, which thus lead to improveme…
Adapting -means algorithms for outliers
Christoph Grunau, Václav Rozhoň
This paper shows how to adapt several simple and classical sampling-based algorithms for the -means problem to the setting with outliers. Recently, Bhaskara et al. (NeurIPS 2019…
Generalizing the Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local Lemma
Sebastian Brandt, Christoph Grunau, Václav Rozhoň
Recently, Brandt, Maus and Uitto [PODC'19] showed that, in a restricted setting, the dependency of the complexity of the distributed Lovász Local Lemma (LLL) on the chosen LLL crit…
Simple and sharp analysis of k-means||
Václav Rozhoň
We present a simple analysis of k-means|| (Bahmani et al., PVLDB 2012) -- a distributed variant of the k-means++ algorithm (Arthur and Vassilvitskii, SODA 2007). Moreover, the boun…
k-means++: few more steps yield constant approximation
Davin Choo, Christoph Grunau, Julian Portmann +1
The k-means++ algorithm of Arthur and Vassilvitskii (SODA 2007) is a state-of-the-art algorithm for solving the k-means clustering problem and is known to give an O(log k)-approxim…
Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization
Václav Rozhoň, Mohsen Ghaffari
We present a simple polylogarithmic-time deterministic distributed algorithm for network decomposition. This improves on a celebrated -time algorithm of Panco…