5 citations · 5 across the 2 of their papers we have counts for
5 papers
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…
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…
Improved Local Computation Algorithm for Set Cover via Sparsification
Christoph Grunau, Slobodan Mitrović, Ronitt Rubinfeld +1
We design a Local Computation Algorithm (LCA) for the set cover problem. Given a set system where each set has size at most and each element is contained in at most sets, t…