Showing cs.DSShow all
3 papers · 1 filter
cs.DS2022
On the Impossibility of Decomposing Binary Matroids
Marilena Leichter, Benjamin Moseley, Kirk Pruhs
We show that there exist -colorable matroids that are not -decomposable when and are constants. A matroid is -decomposable, if its ground set of elements c…
cs.DS2014
SELFISHMIGRATE: A Scalable Algorithm for Non-clairvoyantly Scheduling Heterogeneous Processors
Sungjin Im, Janardhan Kulkarni, Kamesh Munagala +1
We consider the classical problem of minimizing the total weighted flow-time for unrelated machines in the online \emph{non-clairvoyant} setting. In this problem, a set of jobs …
cs.DS2010
The Geometry of Scheduling
Nikhil Bansal, Kirk Pruhs
We consider the following general scheduling problem: The input consists of n jobs, each with an arbitrary release time, size, and a monotone function specifying the cost incurred…