149 citations · 233 across the 9 of their papers we have counts for
5 papers · 1 filter
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…
Efficient Measurement on Programmable Switches Using Probabilistic Recirculation
Ran Ben Basat, Xiaoqi Chen, Gil Einziger +1
Programmable network switches promise flexibility and high throughput, enabling applications such as load balancing and traffic engineering. Network measurement is a fundamental bu…
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…
Heavy Hitters over Interval Queries
Ran Ben Basat, Roy Friedman, Rana Shahout
Heavy hitters and frequency measurements are fundamental in many networking applications such as load balancing, QoS, and network security. This paper considers a generalized slidi…