4 papers
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…
Near-optimal Algorithms for Stochastic Online Bin Packing
Nikhil Ayyadevara, Rajni Dabas, Arindam Khan +1
We study the online bin packing problem under two stochastic settings. In the bin packing problem, we are given n items with sizes in (0,1] and the goal is to pack them into the mi…