58 citations · 72 across the 3 of their papers we have counts for
8 papers · 1 filter
Generalized Assignment via Submodular Optimization with Reserved Capacity
Ariel Kulik, Kanthi Sarpatwar, Baruch Schieber +1
We study a variant of the \emph{generalized assignment problem} ({\sf GAP}) with group constraints. An instance of {\sf Group GAP} is a set of items, partitioned into group…
Scalable Fair Clustering
Arturs Backurs, Piotr Indyk, Krzysztof Onak +3
We study the fair variant of the classic -median problem introduced by Chierichetti et al. [2017]. In the standard -median problem, given an input pointset , the goal is t…
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…