Publications

A Beyond-Worst-Case Analysis of Greedy k-means++. With Qingyun Chen, Ben Moseley, Ryan Milstrey, Chenyang Xu, and Ruilong Zhang. NeurIPS '25

Online Distributed Queue Length Estimation. With Aditya Bhaskara, Sreenivas Gollapudi, Kostas Kollias, and Kamesh Munagala. SIAM Conference on Applied and Computational Discrete Algorithms (ACDA) 25.

Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints. With Benjamin Moseley, Hung Ngo, and Kirk Pruhs. PODS '25

Polynomial Time Convergence of the Iterative Evaluation of Datalogo Programs. With Benjamin Moseley, Hung Ngo, and Kirk Pruhs. PODS '25

Online Scheduling via Gradient Descent for Weighted Flow Time Minimization With Qingyun Chen and Aditya Petety. SODA '25

Strategic Facility Location via Predictions. With Qingyun Chen and Nick Gravin. WINE '24

Binary Search Tree with Distributional Predictions. With Michael Dinitz, Thomas Lavastida, Benjamin Moseley, Aidin Niaparast, and Sergei Vassilvitskii. NeurIPS '24

Online Load and Graph Balancing for Random Order Inputs. With Ravi Kumar, Shi Li, Aditya Petety, and Manish Purohit. SPAA '24 (Outstanding Paper (Best Paper Finalist))

Data Exchange Markets via Utility Balancing. With Aditya Bhaskara, Sreenivas Gollapudi, Kostas Kollias, Kamesh Munagala, and Govind S. Sanka. WWW '24

On the Convergence Rate of Linear Datalogo over Stable Semirings. With Benjamin Moseley, Hung Ngo, and Kirk Pruhs. ICDT '24

Sampling for Beyond-Worst-Case Online Ranking. With Qingyun Chen, Benjamin Moseley, Chenyang Xu, and Ruilong Zhang. AAAI '24

Controlling Tail Risk in Online Ski-Rental. With Michael Dinitz, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. SODA '24

Massively Parallel Computation: Algorithms and Applications. With Ravi Kumar, Silvio Lattanzi, Benjamin Moseley and Sergei Vassilvitskii. Foundations and Trends in Optimization 23

Online State Exploration: Competitive Worst Case and Learning-Augmented Algorithms. With Benjamin Moseley, Chenyang Xu, and Ruilong Zhang. ECML/PKDD 23

Online Dynamic Acknowledgement with Learned Predictions. with Benjamin Moseley, Chenyang Xu, and Ruilong Zhang. INFOCOM '23

Min-Max Submodular Ranking for Multiple Agents. with Qingyun Chen, Benjamin Moseley, Chenyang Xu, and Ruilong Zhang. AAAI '23

Online Learning and Bandits with Queried Hints with Aditya Bhaskara, Sreenivas Gollapudi, Kostas Kollias, and Kamesh Munagala. ITCS '23

Improved Approximations for Unrelated Machine Scheduling with Shi Li. SODA '23

Non-Clairvoyant Scheduling with Predictions with Ravi Kumar, Mahshid Montazer Qaem, and Manish Purohit. ACM TOPC '23 (Journal version of the SPAA '21 paper)

Algorithms with Prediction Portfolios. with Michael Dinitz, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. NeurIPS '22

Parsimonious Learning-Augmented Caching. With Ravi Kumar, Aditya Petety, and Manish Purohit. ICML '22

Faster Matchings via Learned Duals, with Michael Dinitz, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. NeurIPS '21 (Oral Presentation)

Online Knapsack with Frequency Predictions, with Ravi Kumar, Mahshid Montazer Qaem, and Manish Purohit. NeurIPS '21

Non-Clairvoyant Scheduling with Predictions with Ravi Kumar, Mahshid Montazer Qaem, and Manish Purohit. ACM SPAA '21 (Best Paper Finalist)

An Approximation Algorithm for the Matrix Tree Multiplication Problem with Mahmoud Abo Khamis, Ryan Curtin, Benjamin Moseley, Hung Ngo, Kirk Pruhs and Alireza Samadian. MFCS '21

Instance Optimal Join Size Estimation with Mahmoud Abo-Khamis, Benjamin Moseley, Kirk Pruhs, and Alireza Samadian. LAGOS '21

The Matroid Cup Game with Benjamin Moseley and Rudy Zhou. Operations Research Letters '21

A Relational Gradient Descent Algorithm For Support Vector Machine Training with Mahmoud Abo-Khamis, Benjamin Moseley, Kirk Pruhs, and Alireza Samadian. SIAM-ACM Symposium on Algorithmic Principles of Computer Systems (APoCS) '21

Approximate Aggregate Queries Under Additive Inequalities with Mahmoud Abo-Khamis, Benjamin Moseley, Kirk Pruhs, and Alireza Samadian. SIAM-ACM Symposium on Algorithmic Principles of Computer Systems (APoCS) '21

Matroid Set Cover with Benjamin Moseley and Kirk Pruhs. Operations Research Letters '21

Fair Scheduling via Iterative Quasi-Uniform Sampling
with Benjamin Moseley
SICOMP '20 (Preliminary version appeared in SODA '17)

Breaking 1 - 1/e Barrier for Nonpreemptive Throughput Maximization
with Shi Li and Benjamin Moseley
SIAM Journal on Discrete Mathematics '20 (Preliminary version appeared in IPCO '17)

Online Two-dimensional Load Balancing
with Ilan Cohen and Debmalya Panigrahi
ICALP '20

Unconditional Coresets for Regularized Loss Minimization
with Alireza Samadian, Kirk Pruhs, Sungjin Im, and Ryan Curtain
AISTATS '20

Fast Noise Removal for k-means Clustering
with Benjamin Moseley, Mahshid Montazer Qaem, Xiaorui Sun, and Rudy Zhou
AISTATS '20

Dynamic Weighted Fairness with Minimal Disruptions
with Benjamin Moseley, Kamesh Munagala, and Kirk Pruhs
SIGMETRICS '20

Hallucination Helps: Energy Efficient Virtual Circuit Routing
with Antonios Antoniadis, Ravishankar Krishnaswamy, Benjamin Moseley, Viswanath Nagarajan, Kirk Pruhs, and Clifford Stein
SICOMP '20 (Preliminary version appeared in SODA '14)

Weighted Completion Time Minimization for Unrelated Machines via Iterative Fair Contention Resolution
with Maryam Shadloo
SODA '20

Fast and Parallelizable Ranking with Outliers from Pairwise Comparisons
with Mahshid Montazer Qaem
ECMLPKDD '19

Matroid Coflow Scheduling
with Benjamin Moseley, Kirk Pruhs, and Manish Purohit
ICALP '19

Non-clairvoyantly Scheduling to Minimize Convex Functions
with Kyle Fox, Janardhan Kulkarni, and Benjamin Moseley
Algorithmica '19 (Preliminary version appeared in APPROX '13)

Tight Bounds for Online Vector Scheduling
with Nathaniel Kell, Janardhan Kulkarni, and Debmalya Panigrahi
SICOMP '19 (Preliminary version appeared in FOCS '15)

A Conditional Lower Bound on Graph Connectivity in MapReduce
with Benjamin Moseley
Manuscript '19

Competitive Algorithms from Competitive Equilibria: Non-Clairvoyant Scheduling under Polyhedral Constraints
with Janardhan Kulkarni and Kamesh Munagala
JACM '18 (This journal paper combines two preliminary results that appeared in STOC '14 and FOCS '15) errata

Online Load Balancing on Related Machines
with Nathaniel Kell, Debmalya Panigrahi, and Maryam Shadloo
STOC '18

Online Partial Throughput Maximization for Multidimensional Coflow
with Maryam Shadloo and Zizhan Zheng
INFOCOM '18

Energy efficient scheduling of parallelizable jobs
with Kyle Fox and Benjamin Moseley
Thoeretical Computer Science '18 (Preliminary version appeared in SODA '13)

An O(log log m)-competitive Algorithm for Online Machine Minimization
with Benjamin Moseley, Kirk Pruhs, and Cliff Stein
RTSS '17

Minimizing Maximum Flow Time on Related Machines via Dynamic Posted Pricing
with Benjamin Moseley, Kirk Pruhs, and Cliff Stein
ESA '17

Efficient Massively Parallel Methods for Dynamic Programming
with Benjamin Moseley and Xiaorui Sun
STOC '17

Breaking 1 - 1/e Barrier for Non-preemptive Throughput Maximization
with Shi Li and Benjamin Moseley
IPCO '17

Fair Scheduling via Iterative Quasi-Uniform Sampling
with Benjamin Moseley
SODA '17

Minimizing the Maximum Flow Time in Batch Scheduling
with Hoon Oh and Maryam Shadloo
Operations Research Letter '16

Better Unrelated Machine Scheduling for Weighted Completion Time via Random Offsets from Non-Uniform Distributions
with Shi Li
FOCS '16

A Competitive Flow Time Algorithm for Heterogeneous Clusters under Polytope Constraints
with Janardhan Kulkarni, Benjamin Moseley, and Kamesh Munagala
APPROX '16

Min-Sum Set Cover and Its Generalizations
Encyclopedia of Algorithms '16

Brief Announcement: A QPTAS for Non-preemptive Speed-scaling
with Maryam Shadloo
SPAA '16

Fair Online Scheduling for Selfish Jobs on Heterogeneous Machines
with Janardhan Kulkarni
SPAA '16

General Profit Scheduling and the Power of Migration on Heterogeneous Machines
with Benjamin Moseley
SPAA '16

Competitive Analysis of Constrained Queueing Systems
with Janardhan Kulkarni and Kamesh Munagala
ICALP '16

Scheduling Jobs with Non-uniform Demands on Multiple Servers without Interruption
with Mina Naghshnejad and Mukesh Singhal
INFOCOM '16

Minimum Latency Submodular Cover
with Viswanath Nagarajan and Ruben van der Zwaan
ACM TALG '16 (Preliminary result appeared in ICALP '12)

Competitively Scheduling Tasks with Intermediate Parallelizability
with Benjamin Moseley, Kirk Pruhs, and Eric Torng
ACM TOPC '16 (Preliminary result appeared in SPAA '14; invited)

Tight Bounds for Online Vector Scheduling
with Nathaniel Kell, Janardhan Kulkarni, and Debmalya Panigrahi
FOCS '15

Competitive Flow Time Algorithms for Polyhedral Scheduling
with Janardhan Kulkarni and Kamesh Munagala
FOCS '15

On the Randomized Competitive Ratio of Reordering Buffer Management with Non-Uniform Costs
with Noa Avigdor-Elgrabli, Benjamin Moseley, and Yuval Rabani
ICALP '15

Weighted Reordering Buffer Improved via Variants of Knapsack Covering Inequalities
with Benjamin Moseley
ICALP '15

Temporal Fairness of Round Robin: Competitive Analysis for Lk-norms of Flow Time
with Janardhan Kulkarni and Benjamin Moseley
SPAA '15

Scheduling in Bandwidth Constrained Tree Networks
with Benjamin Moseley
SPAA '15

Fast and Better Distributed MapReduce Algorithms for k-Center Clustering
with Benjamin Moseley
SPAA '15 (Brief Announcement)

Stochastic Scheduling of Heavy-tailed Jobs
with Benjamin Moseley and Kirk Pruhs
STACS '15

New Approximations for Broadcast Scheduling via Variants of \alpha-point Rounding
with Maxim Sviridenko
SODA '15

A Dynamic Programming Framework for Non-Preemptive Scheduling Problems on Multiple Machines
with Shi Li, Benjamin Moseley and Eric Torng
SODA '15

SelfishMigrate: A Scalable Algorithm for Non-clairvoyantly Scheduling Heterogeneous Processors
with Janardhan Kulkarni, Kamesh Munagala and Kirk Pruhs
FOCS '14

Competitively Scheduling Tasks with Intermediate Parallelizability
with Benjamin Moseley, Kirk Pruhs and Eric Torng
SPAA '14

Competitive Algorithms from Competitive Equilibria: Non-Clairvoyant Scheduling under Polyhedral Constraints
with Janardhan Kulkarni and Kamesh Munagala
STOC '14

Coordination Mechanisms from (almost) all Scheduling Policies
with Sayan Bhattacharya, Janardhan Kulkarni and Kamesh Munagala
ITCS '14

New Approximations for Reordering Buffer Management
with Benjamin Moseley
SODA '14

Hallucination Helps: Energy Efficient Virtual Circuit Routing
with Antonios Antoniadis, Ravishankar Krishnaswamy, Benjamin Moseley, Vishwanath Nagarajan, Kirk Pruhs and Clifford Stein
SODA '14

Preemptive and non-preemptive generalized min sum set cover
with Maxim Sviridenko and Ruben van der Zwaan
Math Programming '14 (preliminary version appeared in STACS '12)

Online Scheduling with General Cost Functions
with Benjamin Moseley
SICOMP '14 (preliminary version appeared in SODA '12)

Online Non-clairvoyant Scheduling to Simultaneously Minimize All Convex Functions
with Kyle Fox, Janardhan Kulkarni and Benjamin Moseley
APPROX '13

Brief Announcement: Online Batch Scheduling for Flow Objectives
with Benjamin Moseley
SPAA '13

Optimized Scheduling of Multi-IMA Partitions with Exclusive Region for Synchronized Real-Time Multi-Core Systems
Jung-Eun Kim, Man-Ki Yoon, Sungjin Im, Richard Bradford and Lui Sha
Design, Automation & Test in Europe, DATE '13

Energy Efficient Schedulig of Parallelizable Jobs
with Kyle Fox and Benjamin Moseley
24th ACM-SIAM Symposium on Discrete Algorithms , SODA '13

Shortest-Elapsed-Time-First on a Multiprocessor
with Neal Barcelo, Benjamin Moseley and Kirk Pruhs
Mediterranean Conference on Algorithms, MedAlg '12

Online Scheduling Algorithms for Average Flow Time and its Variants
Ph.D. thesis

Speed scaling for stretch plus energy
with Daniel Cole, Benjamin Moseley and Kirk Pruhs
Operations Research Letters

Minimum Latency Submodular Cover
with Viswanath Nagarajan and Ruben Van Der Zwaan
39th International Colloquium on Automata, Languages and Programmig, ICALP '12

Preemptive and Non-preemptive Generalized Min Sum Set Cover
with Maxim Sviridenko and Ruben Van Der Zwaan
Symposium on Theoretical Aspects of Computer Science, STACS '12

Online Scheduling with General Cost Functions
with Benjamin Moseley and Kirk Pruhs
23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '12

Scheduling Heterogeneous Processors Isn't As Easy As You Think
with Anupam Gaupta, Ravishankar Krishnaswamy, Benjamin Moseley and Kirk Pruhs
23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '12

Envy-free Pricing with General Supply Constraints
with Pinyan Lu and Yajun Wang
J. Comput. Sci. Technol. '12 (preliminary version appeared in WINE '10)

An online scalable algorithm for average flow time in broadcast scheduling
with Benjamin Moseley
ACM TALG '12 (preliminary version appeared in SODA '10)

Online Scheduling to Minimize Maximum Response Time and Maximum Delay Factor
with Chandra Chekuri and Benjamin Moseley
Theory of Computing '12

Signature Pattern Covering via Local Greedy Algorithm and Pattern Shrink
Hyungsul Kim, David Sheridan, Sungjin Im, Shobha Vasudevan, Tarek Abdelzaher and Jiawei Han
IEEE International Conference on Data Mining, ICDM '11

Fast Clustering using MapReduce
with Alina Ene and Benjamin Moseley
17th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD '11

A Tutorial on Amortized Local Competitiveness in Online Scheduling
with Benjamin Moseley and Kirk Pruhs
ACM SIGACT NEWS (June 2011)

Secretary Problems: Laminar Matroid and Interval Scheduling
with Yajun Wang
22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '11

Online Scalable Scheduling for the \ell_k-norms of Flow Time Without Conservation of Work
with Jeff Edmonds and Benjamin Moseley
22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '11

An Online Scalable Algorithm for Minimizing \ell_k-norms of Weighted Flow Time on Unrelated Machines
with Benjamin Moseley
22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '11

Envy-free Pricing with General Supply Constraints (short paper)
with Pinyan Lu and Yajun Wang
6th Workshop on Internet and Network Economics, WINE '10

New Models and Algorithms for Throughput Maximization in Broadcast Scheduling
with Chandra Chekuri, Avigdor Gal, Samir Khuller, Jian Li, Richard McCutchen, Benjamin Moseley and Louiqa Raschid
8th Workshop on Approximation and Online Algorithms, WAOA '10

Scheduling Jobs with Varying Parallelizability to Reduce Variance
with Anupam Gupta, Ravishankar Krishnaswamy, Benjamin Moseley and Kirk Pruhs
22nd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '10

An Online Scalable Algorithm for Average Flow Time in Broadcast Scheduling
Best Student Paper Award
with Benjamin Moseley
21st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '10
ACM Transactions on Algorithms 8(4): 39, 2012

Minimizing Maximum Response Time and Delay Factor in Broadcast Scheduling
with Chandra Chekuri and Benjamin Moseley
17th Annual European Symposium on Algorithms, ESA '09

Longest Wait First For Broadcast Scheduling
with Chandra Chekuri and Benjamin Moseley
7th Workshop on Approximation and Online Algorithms, WAOA '09