149 citations · 149 across the 2 of their papers we have counts for
4 papers · 1 filter
Optimal Distributed Covering Algorithms
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…
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…