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…
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…
Online Flexible Busy Time Scheduling on Heterogeneous Machines
Gruia Calinescu, Adrian Calinescu, Sami Davies +2
We study the online busy time scheduling model on heterogeneous machines. In our setting, jobs with uniform processing time arrive online with a deadline that becomes known to the…