4 citations · 15 across the 9 of their papers we have counts for
5 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…
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…
Constrained Submodular Maximization via Greedy Local Search
Kanthi K. Sarpatwar, Baruch Schieber, Hadas Shachnai
We present a simple combinatorial -approximation algorithm for maximizing a monotone submodular function subject to a knapsack and a matroid constraint. This c…
Approximation Algorithms for Connected Maximum Cut and Related Problems
MohammadTaghi Hajiaghayi, Guy Kortsarz, Robert MacDavid +2
An instance of the Connected Maximum Cut problem consists of an undirected graph G = (V, E) and the goal is to find a subset of vertices S V that maximizes the number o…
Analyzing the Optimal Neighborhood: Algorithms for Budgeted and Partial Connected Dominating Set Problems
Samir Khuller, Manish Purohit, Kanthi Sarpatwar
We study partial and budgeted versions of the well studied connected dominating set problem. In the partial connected dominating set problem, we are given an undirected graph G = (…