5 citations · 25 across the 19 of their papers we have counts for
5 papers · 1 filter
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…
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…
Improved MPC Algorithms for MIS, Matching, and Coloring on Trees and Beyond
Mohsen Ghaffari, Christoph Grunau, Ce Jin
We present round scalable Massively Parallel Computation algorithms for maximal independent set and maximal matching, in trees and more generally graphs of bounded…