970 citations · 1.7k across the 49 of their papers we have counts for
3 papers · 2 filters
Optimal Distributed Weighted Set Cover Approximation
Ran Ben-Basat, Guy Even, Ken-ichi Kawarabayashi +1
We present a time-optimal deterministic distributed algorithm for approximating a minimum weight vertex cover in hypergraphs of rank . This problem is equivalent to the Minimum…
Parameterized Distributed Algorithms
Ran Ben-Basat, Ken-ichi Kawarabayashi, Gregory Schwartzman
In this work, we initiate a thorough study of parameterized graph optimization problems in the distributed setting. In a parameterized problem, an algorithm decides whether a solut…
A Deterministic Distributed -Approximation for Weighted Vertex Cover in Rounds
Ran Ben-Basat, Guy Even, Ken-ichi Kawarabayashi +1
We present a deterministic distributed -approximation algorithm for the Minimum Weight Vertex Cover problem in the CONGEST model whose round complexity is $O(\log n \log Δ/ \log…