8 papers
Non-Clairvoyant Scheduling is Hard Even for Trees
Kunal Agrawal, Owen Druzgal, Milind Prabhu +1
We study online scheduling of parallel jobs on identical processors to minimize maximum flow time. Each arriving job is represented by a directed acyclic graph (DAG) whose vert…
The Cube-Root Phenomenon in Online Carpooling
Nikhil Bansal, Milind Prabhu, Sahil Singla +1
We consider the online carpooling problem, where edges arrive online and must be oriented immediately while keeping the discrepancy between the indegree and outdegree at each verte…
Approximation Preserving Coresets
Milind Prabhu, Chris Schwiegelshohn, Sudarshan Shyam
Clustering in a big data setting is an intensively studied problem, with coresets emerging as one of the important paradigms in this line of work. Given a cost function $\text{cost…
Online Graph Balancing and the Power of Two Choices
Nikhil Bansal, Milind Prabhu, Sahil Singla +1
In the classic online graph balancing problem, edges arrive sequentially and must be oriented immediately upon arrival, to minimize the maximum in-degree. For adversarial arrivals,…
Learning Multiple Secrets in Mastermind
Milind Prabhu, David Woodruff
In the Generalized Mastermind problem, there is an unknown subset of the hypercube containing points. The goal is to learn by making a few queries to an ora…
Sensitivity Sampling for -Means: Worst Case and Stability Optimal Coreset Bounds
Nikhil Bansal, Vincent Cohen-Addad, Milind Prabhu +2
Coresets are arguably the most popular compression paradigm for center-based clustering objectives such as -means. Given a point set , a coreset is a small, weighted summ…
On Minimizing Generalized Makespan on Unrelated Machines
Nikhil Ayyadevara, Nikhil Bansal, Milind Prabhu
We consider the Generalized Makespan Problem (GMP) on unrelated machines, where we are given jobs and machines and each job has arbitrary processing time on ma…
Generalizing Greenwald-Khanna Streaming Quantile Summaries for Weighted Inputs
Sepehr Assadi, Nirmit Joshi, Milind Prabhu +1
Estimating quantiles, like the median or percentiles, is a fundamental task in data mining and data science. A (streaming) quantile summary is a data structure that can process a s…