5 papers
Online Span Minimization for Flexible Uniform Jobs
Mozhengfu Liu, Samir Khuller, Xueyan Tang
Motivated by the critical need for energy-efficient scheduling in cloud computing, this paper investigates Span Minimization, a fundamental variant of the well-studied BusyTime pro…
Online Flexible Busy Time Scheduling on Heterogeneous Machines
Gruia Calinescu, Sami Davies, Samir Khuller +1
We study the online busy time scheduling model on heterogeneous machines. In our setting, jobs with uniform length arrive online with a deadline that becomes known to the algorithm…
Capacitated Partition Vertex Cover and Partition Edge Cover
Rajni Dabas, Samir Khuller, Emilie Rivkin
Our first focus is the Capacitated Partition Vertex Cover (C-PVC) problem in hypergraphs. In C-PVC, we are given a hypergraph with capacities on its vertices and a partition of the…
Weighted Partition Vertex and Edge Cover
Rajni Dabas, Samir Khuller, Emilie Rivkin
We study generalizations of the classical Vertex Cover and Edge Cover problems that incorporate group-wise coverage constraints. Our first focus is the \emph{Weighted Prize-Collect…
Facility Location and -Median with Fair Outliers
Rajni Dabas, Samir Khuller, Emilie Rivkin
Classical clustering problems such as \emph{Facility Location} and \emph{-Median} aim to efficiently serve a set of clients from a subset of facilities -- minimizing the total c…