R. Bar-Yehuda

activity

20112020

most citedRandomized Algorithms for the Loop Cutset Problem

82 citations · 86 across the 2 of their papers we have counts for

collaborators

4 papers

cs.DS2020

Distributed Approximation on Power Graphs

Reuven Bar-Yehuda, Keren Censor-Hillel, Yannic Maus +2

We investigate graph problems in the following setting: we are given a graph $G$ and we are required to solve a problem on $G^{2}$ . While we focus mostly on exploring this theme in t…

cs.DC2017★ 4 cited

Distributed Approximation of Maximum Independent Set and Maximum Matching

Reuven Bar-Yehuda, Keren Censor-Hillel, Mohsen Ghaffari +1

We present a simple distributed $Δ$ -approximation algorithm for maximum weight independent set (MaxIS) in the $CONGEST$ model which completes in $O(\texttt{MIS}(G)\cdot \l…

cs.DC2016

A Distributed $(2 + ε)$ -Approximation for Vertex Cover in $O (lo g Δ/ ε lo g lo g Δ)$ Rounds

Reuven Bar-Yehuda, Keren Censor-Hillel, Gregory Schwartzman

We present a simple deterministic distributed $(2 + ε)$ -approximation algorithm for minimum weight vertex cover, which completes in $O (lo g Δ/ ε lo g lo g Δ)$ rounds, where $Δ$ is the max…

cs.AI2011★ 82 cited

Randomized Algorithms for the Loop Cutset Problem

R. Bar-Yehuda, A. Becker, D. Geiger

We show how to find a minimum weight loop cutset in a Bayesian network with high probability. Finding such a loop cutset is the first step in the method of conditioning for inferen…

Distributed Approximation on Power Graphs

Distributed Approximation of Maximum Independent Set and Maximum Matching

A Distributed (2+ε)-Approximation for Vertex Cover in O(logΔ/εloglogΔ) Rounds

Randomized Algorithms for the Loop Cutset Problem

A Distributed $(2 + ε)$ -Approximation for Vertex Cover in $O (lo g Δ/ ε lo g lo g Δ)$ Rounds