58 citations · 72 across the 4 of their papers we have counts for
4 papers · 1 filter
The Preemptive Resource Allocation Problem
Kanthi Sarpatwar, Baruch Schieber, Hadas Shachnai
We revisit a classical scheduling model to incorporate modern trends in data center networks and cloud services. Addressing some key challenges in the allocation of shared resource…
Fully Dynamic MIS in Uniformly Sparse Graphs
Krzysztof Onak, Baruch Schieber, Shay Solomon +1
We consider the problem of maintaining a maximal independent set (MIS) in a dynamic graph subject to edge insertions and deletions. Recently, Assadi, Onak, Schieber and Solomon (ST…
Fully Dynamic Maximal Independent Set with Sublinear in n Update Time
Sepehr Assadi, Krzysztof Onak, Baruch Schieber +1
The first fully dynamic algorithm for maintaining a maximal independent set (MIS) with update time that is sublinear in the number of edges was presented recently by the authors of…
Fully Dynamic Maximal Independent Set with Sublinear Update Time
Sepehr Assadi, Krzysztof Onak, Baruch Schieber +1
A maximal independent set (MIS) can be maintained in an evolving -edge graph by simply recomputing it from scratch in time after each update. But can it be maintained in…