4 citations · 4 across the 1 of their papers we have counts for
6 papers
Models of Smoothing in Dynamic Networks
Uri Meir, Ami Paz, Gregory Schwartzman
Smoothed analysis is a framework suggested for mediating gaps between worst-case and average-case complexities. In a recent work, Dinitz et al.~[Distributed Computing, 2018] sugges…
Finding Subgraphs in Highly Dynamic Networks
Keren Censor-Hillel, Victor I. Kolobov, Gregory Schwartzman
In this paper we consider the fundamental problem of finding subgraphs in highly dynamic distributed networks - networks which allow an arbitrary number of links to be inserted / d…
Improved Distributed Approximations for Maximum Independent Set
Ken-ichi Kawarabayashi, Seri Khoury, Aaron Schild +1
We present improved results for approximating maximum-weight independent set ($\MaxIS$) in the CONGEST and LOCAL models of distributed computing. Given an input graph, let and…
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…
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 model which completes in $O(\texttt{MIS}(G)\cdot \l…
A Distributed -Approximation for Vertex Cover in Rounds
Reuven Bar-Yehuda, Keren Censor-Hillel, Gregory Schwartzman
We present a simple deterministic distributed -approximation algorithm for minimum weight vertex cover, which completes in rounds, where is the max…