Ben Moseley Professor
moseleyb@andrew.cmu.edu

Publications by Topic

Notice: A paper below may not be the most recent version. Send me an e-mail if you are interested in an up to date copy. The copyright of the published papers below have been transferred to the respective publishers.

Topics:

Foundations of Machine Learning

Resource Allocation

Energy Efficient Computing

Web Advertising

Foundations of Machine Learning :

Optimal Convergence of Iterative Methods for Datalogo
with: Simon Frisk, Hangdong Zhao, Kirk Pruhs, Sungjin Im, Hung Ngo and Paraschos Koutris
Symposium on Principles of Database Systems (PODS 2025)

• Online Correlation Clustering: Simultaneously Optimizing All $\ell_p$-Norms
  with: Sami Davies and Heather Newman
  International Colloquium on Automata, Languages, and Programming (ICALP 2026)
  
  
• Beyond-Worst-Case Analysis of Greedy k-means++
  with: Qingyun Chen, Sungjin Im, Ryan Milstrey, Chenyang Xu, and Ruilong Zhang
  Neural Information Processing Systems (NeurIPS 2025)
  
  
• Faster Global Minimum Cut with Predictions
  with: Helia Niaparast, and Karan Singh
  International Conference on Machine Learning (ICML 2025)
  
  
• Incremental Approximate Single-Source Shortest Paths with Predictions
  with: Samuel McCauley Aidin Niaparast, Helia Niaparast and Shikha Singh
  International Colloquium on Automata, Languages, and Programming (ICALP 2025)
  
  
• The Nonstationary newsvendor with (and without) Predictions 
  with: Lin An, Andrew Li,and R. Ravi
  Manufacturing and Service Operations Management (MSOM). Accepted 2025.
  
  
• Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints
  with: Sungjin Im, Hung Ngo and Kirk Pruhs
  Symposium on Principles of Database Systems (PODS 2025)
  
  
• Polynomial Time Convergence of the Iterative Evaluation of Datalogo Programs
  with: Sungjin Im, Hung Ngo and Kirk Pruhs
  Symposium on Principles of Database Systems (PODS 2025)
  
  
• Binary Search Tree with Distributional Predictions
  with: Michael Dinitz, Sungjin Im, Thomas Lavastida, Aidin Niaparast, and Sergei Vassilvitskii
  Neural Information Processing Systems (NeurIPS 2024)
  
  
• Online k-Median with Consistent Clusters
  with: Heather Newman and Kirk Pruhs
  International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2024)
  
  
• Incremental Topological Ordering and Cycle Detection with Predictions
  with: Samuel McCauley Aidin Niaparast, and Shikha Singh
  International Conference on Machine Learning (ICML 2024)
  
  
• Simultaneously Approximating All lp-norms in Correlation Clustering
  with: Sami Davies, and Heather Newman
  International Colloquium on Automata, Languages, and Programming (ICALP 2024)
  
  
• Sampling for Beyond-Worst-Case Online Ranking
  with: Qingyun Chen, Sungjin Im, Chenyang Xu, and Ruilong Zhang
  AAAI Confernce on Artificial Intelligence (AAAI 2024)
  
  
• On the Convergence Rate of Linear Datalogoover Stable Semirings
  with: Sungjin Im, Hung Ngo, and Kirk Pruhs
  International Conference on Database Theory (ICDT 2024)
  
  
• Massively Parallel Computation: Algorithms and Applications
  with: Sungjin Im, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii
  Foundations and Trends in Optimization (FnT)
  Book/Tutorial on Massively Parallel Algorithms
  
  
• Online List Labeling with Predictions
  with: Samuel McCauley Aidin Niaparast, and Shikha Singh
  Neural Information Processing Systems (NeurIPS 2023)
  Spotlight Presentation.
  
  
• Fast Combinatorial Algorithms for Min Max Correlation Clustering
  with: Sami Davies and Heather Newman
  International Conference on Machine Learning(ICML 2023)
  
  
• Predictive Flows for Faster Ford-Fulkerson
  with: Sami Davies, Sergei Vassilvitskii, and Yuyan Wang
  International Conference on Machine Learning(ICML 2023)
  
  
• Online Dynamic Acknowledgement with Learned Predictions
  with: Sungjin Im, Chenyang Xu, and Ruilong Zhang
  IEEE International Conference on Computer Communications (INFOCOM 2023)
  
  
• Min-Max Submodular Ranking for Multiple Agents
  with: Qingyun Chen, Sungjin Im, Chenyang Xu, and Ruilong Zhang
  AAAI Confernce on Artificial Intelligence (AAAI 2023)
  
  
• Online State Exploration: Competitive Worst Case and Learning-Augmented Algorithms
  with: Sungjin Im, Chenyang Xu, and Ruilong Zhang
  European Conference on Machine Learning (ECML 2023)
  
  
• Algorithms with Prediction Portfolios
  with: Michael Dinitz, Sungjin Im, Thomas Lavastida, and Sergei Vassilvitskii
  Neural Information Processing Systems (NeurIPS 2022)
  
  
• Learning-Augmented Algorithms for Online Steiner Tree
  with: Chenyang Xu
  AAAI Confernce on Artificial Intelligence (AAAI 2022)
  
  
• Faster Matchings via Learned Duals
  with: Michael Dinitz, Sungjin Im, Thomas Lavastida, and Sergei Vassilvitskii
  Neural Information Processing Systems (NeurIPS 2021)
  Oral Presentation. Orals had a less than 1% acceptence rate.
  
  
• Robust Online Correlation Clustering
  with: Silvio Lattanzi, Sergei Vassilvitskii, Yuyan Wang, and Rudy Zhou
  Neural Information Processing Systems (NeurIPS 2021)
  
  
• Structural Iterative Rounding for Generalized k-Median Problems
  with: Anupam Gupta and Rudy Zhou
  International Colloquium on Automata, Languages, and Programming (ICALP 2021)
  
  
• Relational Algorithms for k-means Clustering
  with: Kirk Pruhs, Alireza Samadian and Yuyan Wang
  International Colloquium on Automata, Languages, and Programming (ICALP 2021)
  
  
• Hierarchical Clustering in General Metric Spaces using Approximate Nearest Neighbors
  with: Sergei Vassilvitskii and Yuyan Wang
  In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS 2021)
  
  
  
• Learnable and Instance-Robust Predictions for Online Matching, Flows and Load Balancing
  with: Thomas Lavastida, R. Ravi and Chenyang Xu
  European Symposium on Algorithms (ESA 2021)
  
  
• Scaling Average-Linkage via Sparse Cluster Embeddings
  with: Kefu Lu, Thomas Lavastida, and Yuyan Wang
  Asian Conference on Machine Learning (ACML 2021)
  
  
• An Approximation Algorithm for the Matrix Tree Multiplication Problem
  with: Mahmoud Abo Khamis, Ryan Curtin, Sungjin Im, Hung Ngo, Kirk Pruhs and Alireza Samadian
  Mathematical Foundations of Computer Science (MFCS 2021)
  
  
• Using Predicted Weights for Ad Delivery
  with: Thomas Lavastida, R. Ravi and Chenyang Xu
  SIAM Conference on Applied and Computational Discrete Algorithms (ACDA 2021)
  
  
• A Scalable Approximation Algorithm for Weighted Longest Common Subsequence
  with: Jeremy Buhler, Thomas Lavastida, and Kefu Lu
  In Proceedings of the International European Conference on Parallel and Distributed Computing (Euro-Par 2021)
  
  
  
• Instance Optimal Join Size Estimation
  with: Mahmoud Abo-Khamis, Sungjin Im, Kirk Pruhs, and Alireza Samadian
  Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS 2021)
  
  
  
• Approximate Aggregate Queries Under Additive Inequalities
  with: Mahmoud Abo-Khamis, Sungjin Im, Kirk Pruhs, and Alireza Samadian
  SIAM-ACM Symposium on Algorithmic Principles of Computer Systems (APoCS 2021)
  
  
  
• A Relational Gradient Descent Algorithm For Support Vector Machine Training
  with: Mahmoud Abo-Khamis, Sungjin Im, Kirk Pruhs, and Alireza Samadian
  SIAM-ACM Symposium on Algorithmic Principles of Computer Systems (APoCS 2021)
  
  
  
• Fair Hierarchical Clustering
  with: Sara Ahmadian, Alessandro Epasto, Marina Knittel, Ravi Kumar, Mohammad Mahdian, Philip Pham, Sergei Vassilvitskii and Yuyan Wang
  Neural Information Processing System (NeurIPS 2020)
  
  
  
• Fast Noise Removal for k-means Clustering
  with: Sungjin Im, Mashid Qaem, Xiaorui Sun, and Rudy Zhou
  In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS 2020)
  
  
• Unconditional Coresets for Regularized Loss Minimization
  with: Alireza Samadian, Kirk Pruhs, Sungjin Im, and Ryan Curtain
  In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS 2020)
  
  
• Rk-means: Fast Clustering for Relational Data
  with:Ryan Curtain, Hung Ngo, XuanLong Nguyen, Dan Olteanu, Maximillian Schleich
  In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS 2020)
  
  
• An Objective for Hierarchical Clustering in Euclidean Space and its Connection to Bisecting K-means
  with: Yuyan Wang
  AAAI Conference on Artificial Intelligence (AAAI 2020)
  
  
• Online Scheduling via Learned Weights
  with: Silvio Lattanzi, Thomas Lavastida, and Sergei Vassilvitskii
  ACM-SIAM Symposium on Discrete Algorithms (SODA 2020)
  
  
• Cost Effective Active Search
  with: Shali Jiang and Roman Garnett
  Advances in Neural Information Processing Systems (NuerIPS 2019)
  
  
• Backprop with Approximate Activations for Memory-efficient Network Training
  with: Ayan Chakrabarti
  Advances in Neural Information Processing Systems (NuerIPS 2019)
  Project Page with Source Code
  
  
• A Framework for Parallelizing Hierarchical Clustering Methods
  with: Silvio Lattanzi, Thomas Lavastida, and Kefu Lu
  European Conference on Machine Learning (ECML 2019)
  
  
  
• On Functional Aggregate Queries with Additive Inequalities
  with: Mahmoud Abo Khamis, Ryan Curtin, Hung Ngo, Long Nguyen, Dan Olteanu and Maximilian Schleich
  ACM Symposium on Principals of Database Systems (PODS 2019)
  
  
  
• Efficient Nonmyopic Batch Active Search
  with: Shali Jiang, Gustavo Malkomes, Matthew Abbott, and Roman Garnett
  Advances in Neural Information Processing Systems (NuerIPS 2018)
  Spotlight Presentation.
  
  
• Approximation Bounds for Hierarchical Clustering: Average-Linkage, Bisecting K-means, and Local Search
  with: Joshua Wang
  Advances in Neural Information Processing Systems (NIPS 2017).
  Oral Presentation
  
  
  
• Efficient Nonmyopic Active Search
  with: Shali Jiang, Gustavo Malkomes, Geoff Converse, Alyssa Shofner, and Roman Garnett
  International Conference on Machine Learning (ICML 2017)
  
  
  
• Efficient Massively Parallel Methods for Dynamic Programming
  with: Sungjin Im and Xiaorui Sun
  Symposium on Theory of Computing (STOC 2017)
  
  
  
• Cooperative Set Function Optimization Without Communication or Coordination
  with: Gustavo Malkomes, Kefu Lu, Blakeley Hoffman, Roman Garnett, and Richard Mann
  Conference on Autonomous Agents and Multiagent Systems (AAMAS 2017)
  
  
  
• Local Search Methods for k-Means with Outliers
  with: Shalmoli Gupta, Ravi Kumar, Kefu Lu and Sergei Vassilvitskii
  International Conference on Very Large Data Bases (VLDB 2017)
  
  
  
• Fast Distributed k-Center Clustering with Outliers on Massive Data
  with: Gustavo Malkomes, Matt Kusner, Wenlin Chen, and Kilian Weinberger
  Neural Information Processing Systems (NIPS 2015)
  
  
  
• k-Means Clustering on Two-Level Memory Systems
  with: Michael A. Bender, Jonathan Berry, Simon D. Hammond, Branden Moore, and Cynthia A. Phillips
  International Symposium on Memory Systems (MEMSYS 2015)
  
  
  
• Fast and Better Distributed MapReduce Algorithms for k-Center Clustering
  with: Sungjin Im
  ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2015) Brief Announcement
  
  
  
• Two-Level Main Memory Co-Design: Multi-Threaded Algorithmic Primitives, Analysis, and Simulation
  with: Michael A. Bender, Jonathan W Berry, Simon Hammond, Karl Hemmert, Samuel McCauley, Branden Moore, Cynthia A Phillips, David Resnick, and Arun Rodrigues
  Awarded Best Paper
  International Parallel and Distributed Processing Symposium (IPDPS 2015)
  
  
  
• Fast Greedy Algorithms in MapReduce and Streaming
  with: Ravi Kumar, Sergei Vassilvitskii and Andrea Vattani
  Awarded Best Paper
  ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2013)
  
  
  
• Scalable K-Means++
  with: Bahman Bahmani, Andrea Vattani, Ravi Kumar and Sergei Vassilvitskii
  International Conference on Very Large Data Bases (VLDB 2012)
  
  
  
• Fast Clustering using MapReduce
  with: Alina Ene and Sungjin Im
  ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 2011) Oral Presentation.
  
  
  
• Filtering: A Method for Solving Graph Problems in MapReduce
  with: Silvio Lattanzi, Siddharth Suri and Sergei Vassilvitskii
  ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2011)
  
  
  
  
  
  

  Resource Allocation:

  • Minimizing Completion Times of Stochastic Jobs on Parallel Machines is Hard
    with: Kirk Pruhs, Marc Uetz, and Rudy Zhou
    Workshop on Approximation and Online Algorithms (WAOA 2026)
    
    
  • Approximation Algorithms for Matroid-Intersection Coloring with Applications to Rota's Basis Conjecture
    with: Stephen Arndt, Kirk Pruhs, Chaitanya Swamy, and Michael Zlatin
    Foundations of Computer Science (FOCS 2026)
    
    
  • Efficiently Coloring the Intersection of a General Matroid and Combinatorial Matroids
    with: Stephen Arndt, Kirk Pruhs and Michael Zlatin
    Conference on Integer Programming and Combinatorial Optimization (IPCO 2026)
    
    
  • Bayesian Probing on Graphs
    with: Anupam Gupta and Rudy Zhou
    Conference on Integer Programming and Combinatorial Optimization (IPCO 2026)
    
    
  • Competitive Online Transportation Simplified
    with: Stephen Arndt, Kirk Pruhs, and Marc Uetz
    Symposium on Simplicity in Algorithms (SOSA 2026)
    
    
  • Managing High-Bandwidth Memory is a Parallel Scheduling Problem
    with: Kunal Agrawal, Michael Bender, Kirk Pruhs and Cliff Stein
    Symposium on Parallel Algorithms and Architectures (SPAA 2025)
    
    
  • Robust Gittins for Stochastic Scheduling 
    with: Heather Newman, Kirk Pruhs, and Rudy Zhou
    Proceedings of the ACM on Measurement and Analysis of Computing Systems (SIGMETRICS 2025)
    
    
  • Putting Off the Catching Up: Online Joint Replenishment Problem with Holding and Backlog Costs 
    with: Aidin Niaparast and R. Ravi
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2025)
    
    
  • Scheduling Out-Trees Online to Optimize Maximum Flow
    with: Kunal Agrawal, Heather Newman, and Kirk Pruhs
    Symposium on Parallel Algorithms and Architectures (SPAA 2024)
    
    
  • Controlling Tail Risk in Online Ski-Rental 
    with: Michael Dinitz, Sungjin Im, Thomas Lavastida, Sergei Vassilvitskii
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2024)
    
    
    
  • The Public University Secretary Problem 
    with: Heather Newman and Kirk Pruhs
    SIAM Symposium on Simplicity in Algorithms (SOSA 2024)
    
    
    
  • Configuration Balancing for Stochastic Requests  
    with: Franziska Eberle, Anupam Gupta, Nicole Megow and Rudy Zhou
    Conference on Integer Programming and Combinatorial Optimization (IPCO 2023)
    
    
    
  • Minimizing Completion Times for Stochastic Jobs via Batched Free Times
    with: Anupam Gupta and Rudy Zhou
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)
    
    
  • Online Scheduling of Parallelizable jobs in the Directed Acyclic Graphs and Speed-up Curves Models
    with: Ruilong Zhang and Shanjiawen Zhao
    Theoretical Compuer Science
    
    
  • On the Impossibility of Decomposing Binary Matroids      
    with: Marilena Leichter and Kirk Pruhs
    Operations Research Letters (ORL)
    
    
    
  • A Competitive Algorithm for Throughout Maximization on Identical Machines  
    with: Kirk Pruhs, Clifford Stein, and Rudy Zhou
    Conference on Integer Programming and Combinatorial Optimization (IPCO 2022)
    
    
    
  • Automatic HBM Management: Models and Algorithms  
    with: Kunal Agrawal, Michael Bender, Jonathan Berry, Rathish Das , Daniel DeLayo, Cynthia Phillips and Kenny Zhang
    Symposium on Parallel Algorithms and Architectures (SPAA 2022)
    
    
    
  • The Efficiency-Fairness Balance of Round Robin Scheduling  
    with: Shai Vardi
    Operations Research Letters (ORL)
    
    
    
  • The Case for Phase-Aware Scheduling
    with: Benjamin Berg, Mor Harchol-Balter, Justin Whitehouse, Weina Wang
    International Symposium on Computer Performance, Modeling, Measurements and Evaluation (Performance 2021)
    
    
  • An Efficient Reduction of a Gammoid to a Partition Matroid
    with: Marilena Leichter and Kirk Pruhs
    European Symposium on Algorithms (ESA 2021)
    
    
  • The Matroid Cup Game
    with: Sungjin Im and Rudy Zhou
    Operations Research Letters (ORL)
    
    
    
  • The Matroid Intersection Cover Problem
    with: Sungjin Im and Kirk Pruhs
    Operations Research Letters (ORL)
    
    
    
  • How to Manage High-Bandwidth Memory Automatically
    with: Rathish Das, Kunal Agrawal, Michael Bender, Jonathan Berry, Benjamin Moseley and Cynthia Phillips
    ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2020)
    
    
    
  • Optimal Resource Allocation for Elastic and Inelastic Jobs
    with: Benjamin Berg, Mor Harchol-Balter, Justin Whitehouse, and Weina Wang
    ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2020)
    
    
    
  • Dynamic Weighted Fairness with Minimal Disruptions
    with: Sungjin Im, Kamesh Munagala, and Kirk Pruhs
    Proceedings of the ACM on Measurement and Analysis of Computing Systems (POMACS) (SIGMETRICS 2020)
    
    
    
  • Scheduling for Weighted Flow and Completion Times in Reconfigurable Networks
    with: Michael Dinitz
    IEEE International Conference on Computer Communications (INFOCOM 2020)
    
    
    
  • A Scheduling Approach to Incremental Maintenance of Datalog Programs
    with: Shikha Singh, Sergey Madaminov, Michael Bender, Michael Ferdman, Ryan Johnson, Hung Ngo, Dung Nguyen, Soeren Olesen, Kurt Stirewalt, and Geoffrey Washburn
    IEEE International Parallel and Distributed Processing Symposium (IPDPS 2020).
    
    
    
  • Online Non-preemptive Scheduling to Minimize Maximum Weighted Flow-time on Related Machines
    with: Giorgio Lucarelli, Nguyen Thang, Abhinav Srivastav and Denis Trystram
    Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
    
    
    
  • SubmodularSubmodular Optimization with Contention Resolution Extensions
    with: Maxim Sviridenko
    International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2019)
    
    
    
  • Scheduling to Approximate Minimization Objectives on Identical Machines
    with:
    International Colloquium on Automata, Languages, and Programming (ICALP 2019)
    
    
    
  • Matroid Coflow Scheduling
    with: Sungjin Im, Kirk Pruhs and Manish Purohit
    International Colloquium on Automata, Languages, and Programming (ICALP 2019)
    
    
    
  • Practically Efficient Scheduler for Minimizing Average Flow Time of Parallel Jobs
    with: Kunal Agrawal, I-Ting Angelina Lee, Jing Li and Kefu Lu
    IEEE International Parallel & Distributed Processing Symposium (IPDPS 2019)
    
    
    
  • Online Non-Preemptive Scheduling to Minimize Weighted Flow-time on Unrelated Machines
    with: Giorgio Lucarelli, Nguyen Kim Thang, Abhinav Srivastav and Denis Trystram
    European Symposium on Algorithms (ESA 2018)
    
    
    
  • Online Non-preemptive Scheduling on Unrelated Machines with Rejections
    with: Giorgio Lucarelli, Nguyen Kim Thang, Abhinav Srivastav and Denis Trystram
    ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2018)
    
    
    
  • Scheduling Parallelizable Jobs Online to Maximize Throughput
    with: Kefu Lu, Kunal Agrawal, and Jing Li
    Latin American Theoretical Informatics (LATIN 2018)
    
    
    
  • An O(log log m)-competitive Algorithm for Online Machine Minimization
    with: Sungjin Im, Kirk Pruhs and Clifford Stein
    Real Time Systems Symposium (RTSS 2017)
    
    
    
  • Minimizing Maximum Flow Time on Related Machines via Dynamic Posted Pricing
    with: Sungjin Im, Kirk Pruhs and Clifford Stein
    European Symposium on Algorithms (ESA 2017)
    
    
    
  • Scheduling Parallelizable Jobs Online to Maximize Throughput
    with: Kunal Agrawal, Jing Li, and Kefu Lu
    ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2017) Brief Announcement
    
    
    
  • Breaking 1 - 1/e Barrier for Non-preemptive Throughput Maximization
    with: Sungjin Im and Shi Li
    Conference on Integer Programming and Combinatorial Optimization (IPCO 2017)
    
    
    
  • Stochastic Online Scheduling on Unrelated Machines
    with: Varun Gupta, Marc Uetz and Qiaomin Xie
    Conference on Integer Programming and Combinatorial Optimization (IPCO 2017)
    A journal version is published at Mathematics of Operations Research. The paper contains an error and a correction with slightly looser bounds is published here.
    
    
  • Fair Scheduling via Iterative Quasi-Uniform Sampling
    with: Sungjin Im
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2017)
    
    
    
  • A Competitive Flow Time Algorithm for Heterogeneous Clusters under Polytope ConstraintsM
    with: Sungjin Im, Janardhan Kulkarni, and Kamesh Munagala
    International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2016)
    
    
    
  • General Profit Scheduling and the Power of Migration on Heterogeneous Machines
    with: Sungjin Im
    ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2016)
    
    
    
  • Scheduling Parallelizable Jobs Online to Minimize Maximum Flow Time
    with: Kunal Agrawal, Jing Li, and Kefu Lu
    ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2016)
    
    
    
  • Partitioned Feasibility Tests for Sporadic Tasks on Heterogeneous Machines
    with: Shaurya Ahuja and Kefu Lu
    IEEE International Parallel & Distributed Processing Symposium (IPDPS 2016)
    
    
    
  • Scheduling Parallel DAG Jobs Online to Minimize Average Flow Time
    with: Kunal Agrawal, Jing Li, and Kefu Lu
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2016)
    
    
    
  • Scheduling Parallel Jobs Online with Convex and Concave Parallelizability
    with: Roozbeh Ebrahimi and Samuel McCauley
    Workshop on Approximation and Online Algorithms (WAOA 2015)
    
    
    
  • Weighted Reordering Buffer Improved via Variants of Knapsack Covering Inequalities
    with: Sungjin Im
    International Colloquium on Automata, Languages, and Programming (ICALP 2015)
    
    
    
  • On the Randomized Competitive Ratio of Reordering Buffer Management with Non-Uniform Costs
    with: Noa Avigdor-Elgrabli, Sungjin Im, and Yuval Rabani
    International Colloquium on Automata, Languages, and Programming (ICALP 2015)
    
    
    
  • Temporal Fairness of Round Robin: Competitive Analysis for Lk-norms of Flow Time
    with: Sungjin Im and Janardhan Kulkarni
    ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2015)
    
    
    
  • Scheduling in Bandwidth Constrained Tree Networks
    with: Sungjin Im
    ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2015)
    
    
    
  • Stochastic Scheduling of Heavy-tailed Jobs
    with: Sungjin Im and Kirk Pruhs
    Symposium on Theoretical Aspects of Computer Science (STACS 2015)
    
    
    
  • A Dynamic Programming Framework for Non-Preemptive Scheduling Problems on Multiple Machines
    with: Sungjin Im, Shi Li, and Eric Torng
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2015)
    
    
    
  • Competitively Scheduling Tasks with Intermediate Parallelizability
    with: Sungjin Im, Kirk Pruhs, Eric Torng
    ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2014)
    
    
    
  • Scheduling to Minimize Energy and Flow Time in Broadcast Scheduling
    with:
    Journal of Scheduling
    
    
  • Packet Forwarding Algorithms in a Line Network
    with: Antonios Antoniadis, Neal Barcelo, Daniel Cole, Kyle Fox, Michael Nugent and Kirk Pruhs
    Latin American Theoretical Informatics Symposium (LATIN 2014)
    
    
    
  • Hallucination Helps: Energy Efficient Virtual Circuit Routing
    with: Antonios Antoniadis, Sungjin Im, Ravishankar Krishnaswamy, Vishwanath Nagarajan, Kirk Pruhs and Cliff Stein
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2014)
    
    
    
  • New Approximations for Reordering Buffer Management
    with: Sungjin Im
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2014)
    
    
    
  • Online Non-clairvoyant Scheduling to Simultaneously Minimize All Convex Functions
    with: Kyle Fox, Sungjin Im and Janardhan Kulkarni
    International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2013).
    
    
    
  • Online Batch Scheduling for Flow Objectives
    with: Sungjin Im
    ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2013) Brief Announcement
    
    
    
  • The Complexity of Scheduling for p-norms of Flow and Stretch
    with: Kirk Pruhs and Cliff Stein
    Conference on Integer Programming and Combinatorial Optimization (IPCO 2013)
    
    
    
  • Energy Efficient Scheduling of Parallelizable Jobs
    with: Kyle Fox and Sungjin Im
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2013)
    
    
    
  • Shortest-Elapsed-Time-First on a Multiprocessor
    with: Neal Barcelo, Sungjin Im and Kirk Pruhs
    Mediterranean Conference on Algorithms (MedAlg 2012)
    
    
    
  • Speed Scaling for Total Stretch Plus Energy
    with: Daniel Cole, Sungjin Im and Kirk Pruhs
    Operations Research Letters
    
    
    
  • Online Scheduling with General Cost Functions
    with: Sungjin Im and Kirk Pruhs
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2012)
    
    
  • Scheduling Heterogeneous Processors Isn't As Easy As You Think
    with: Anupam Gupta, Sungjin Im, Ravishankar Krishnaswamy and Kirk Pruhs
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2012)
    
    
    
  • A Tutorial on Amortized Local Competitiveness in Online Scheduling
    with: Sungjin Im and Kirk Pruhs
    A tutorial on the popular potential function technique for online scheduling problems.
    ACM SIGACT News (June 2011)
    
    
    
  • On Scheduling in Map-Reduce and Flow-Shops
    with: Anirban Dasgupta, Ravi Kumar and Tamas Sarlos
    ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2011)
    
    
    
  • Online Scheduling on Identical Machines using SRPT
    with: Kyle Fox
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2011)
    
    
    
  • Online Scalable Scheduling for the \ell_k-norms of Flow Time Without Conservation of Work
    with: Jeff Edmonds and Sungjin Im
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2011)
    
    
    
  • An Online Scalable Algorithm for Minimizing \ell_k-norms of Weighted Flow Time on Unrelated Machines
    with: Sungjin Im
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2011)
    
    
  • New Models and Algorithms for Throughput Maximization in Broadcast Scheduling
    with: Chandra Chekuri, Avigdor Gal, Sungjin Im, Samir Khuller, Jian Li, Richard McCutchen and Louiqa Raschid
    Workshop on Approximation and Online Algorithms (WAOA 2010)
    
    
    
  • Scheduling Jobs with Varying Parallelizability to Reduce Variance
    with: Anupam Gupta, Sungjin Im, Ravishankar Krishnaswamy and Kirk Pruhs
    ACM Symposium on Parallelism in Algorithms and Architectures
    (SPAA 2010)
    
    
    
  • An Online Scalable Algorithm for Average Flowtime in Broadcast Scheduling
    with: Sungjin Im
    Awarded Best Student Paper
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2010)
    Journal Version: ACM Transactions on Algorithms
    
    
    
  • Minimizing Maximum Response Time and Delay Factor in Broadcast Scheduling
    with: Chandra Chekuri and Sungjin Im
    European Symposium on Algorithms (ESA 2009)
    Journal Version (Combines the results of this paper and the SODA 2009 paper below):
    Theory of Computing: Special Issue in honor of Rajeev Motwani
    
    
    
  • Longest Wait First For Broadcast Scheduling
    with: Chandra Chekuri and Sungjin Im
    Workshop on Approximation and Online Algorithms (WAOA 2009)
    
    
    
  • Online Scheduling to Minimize the Maximum Delay Factor
    with: Chandra Chekuri
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2009)
    
  
  
  
  
  

  Energy Efficient Computing:

  • Scheduling to Minimize Energy and Flow Time in Broadcast Scheduling
    with:
    Journal of Scheduling
    
    
  • Hallucination Helps: Energy Efficient Virtual Circuit Routing
    with: Antonios Antoniadis, Sungjin Im, Ravishankar Krishnaswamy, Vishwanath Nagarajan, Kirk Pruhs and Cliff Stein
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2014)
    
    
    
  • Energy Efficient Scheduling of Parallelizable Jobs
    with: Kyle Fox and Sungjin Im
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2013)
    
    
    
  • Speed Scaling for Total Stretch Plus Energy
    with: Daniel Cole, Sungjin Im and Kirk Pruhs
    Operations Research Letters
    
    
    
  • Scheduling Heterogeneous Processors Isn't As Easy As You Think
    with: Anupam Gupta, Sungjin Im, Ravishankar Krishnaswamy and Kirk Pruhs
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2012)
    
    
    
    
    
    

  Web Advertising:

  • Bargaining for Revenue Shares on Tree Trading Networks
    with: Arpita Ghosh, Satyen Kale, and Kevin Lang
    International Joint Conference on Artificial Intelligence (IJCAI 2013) Oral Presentation and Poster
    
    
    
  • Handling Forecast Errors while Bidding for Display Advertising
    with: Kevin Lang and Sergei Vassilvitskii
    International Conference on World Wide Web (WWW 2012)