Publications by Year

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.


    2026

  1. Competitive Online Transportation Simplified
    with: Stephen Arndt, Kirk Pruhs, and Marc Uetz
    Symposium on Simplicity in Algorithms (SOSA 2026)

    2025

  2. 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)

  3. 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)

  4. Faster Global Minimum Cut with Predictions
    with: Helia Niaparast, and Karan Singh
    International Conference on Machine Learning (ICML 2025)

  5. 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)

  6. 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)

  7. The Nonstationary newsvendor with (and without) Predictions 
    with: Lin An, Andrew Li,and R. Ravi
    Manufacturing and Service Operations Management (MSOM). Accepted 2025.

  8. 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)

  9. 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)

  10. 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)

    2024

  11. Binary Search Tree with Distributional Predictions
    with: Michael Dinitz, Sungjin Im, Thomas Lavastida, Aidin Niaparast, and Sergei Vassilvitskii
    Neural Information Processing Systems (NeurIPS 2024)

  12. Online k-Median with Consistent Clusters
    with: Heather Newman and Kirk Pruhs
    International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2024)

  13. Incremental Topological Ordering and Cycle Detection with Predictions
    with: Samuel McCauley Aidin Niaparast, and Shikha Singh
    International Conference on Machine Learning (ICML 2024)

  14. Simultaneously Approximating All lp-norms in Correlation Clustering
    with: Sami Davies, and Heather Newman
    International Colloquium on Automata, Languages, and Programming (ICALP 2024)

  15. Scheduling Out-Trees Online to Optimize Maximum Flow
    with: Kunal Agrawal, Heather Newman, and Kirk Pruhs
    Symposium on Parallel Algorithms and Architectures (SPAA 2024)

  16. Sampling for Beyond-Worst-Case Online Ranking
    with: Qingyun Chen, Sungjin Im, Chenyang Xu, and Ruilong Zhang
    AAAI Confernce on Artificial Intelligence (AAAI 2024)

  17. Controlling Tail Risk in Online Ski-Rental 
    with: Michael Dinitz, Sungjin Im, Thomas Lavastida, and Sergei Vassilvitskii
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2024)

  18. The Public University Secretary Problem 
    with: Heather Newman and Kirk Pruhs
    SIAM Symposium on Simplicity in Algorithms (SOSA 2024)

  19. On the Convergence Rate of Linear Datalogoover Stable Semirings
    with: Sungjin Im, Hung Ngo, and Kirk Pruhs
    International Conference on Database Theory (ICDT 2024)

    2023

  20. 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

  21. Online List Labeling with Predictions
    with: Samuel McCauley Aidin Niaparast, and Shikha Singh
    Neural Information Processing Systems (NeurIPS 2023)
    Spotlight Presentation.

  22. Fast Combinatorial Algorithms for Min Max Correlation Clustering
    with: Sami Davies and Heather Newman
    International Conference on Machine Learning(ICML 2023)

  23. Predictive Flows for Faster Ford-Fulkerson
    with: Sami Davies, Sergei Vassilvitskii, and Yuyan Wang
    International Conference on Machine Learning(ICML 2023)

  24. Configuration Balancing for Stochastic Requests  
    with: Franziska Eberle, Anupam Gupta, Nicole Megow and Rudy Zhou
    Conference on Integer Programming and Combinatorial Optimization (IPCO 2023)


  25. Minimizing Completion Times for Stochastic Jobs via Batched Free Times
    with: Anupam Gupta and Rudy Zhou
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)

  26. Online Dynamic Acknowledgement with Learned Predictions
    with: Sungjin Im, Chenyang Xu, and Ruilong Zhang
    IEEE International Conference on Computer Communications (INFOCOM 2023)

  27. Min-Max Submodular Ranking for Multiple Agents
    with: Qingyun Chen, Sungjin Im, Chenyang Xu, and Ruilong Zhang
    AAAI Confernce on Artificial Intelligence (AAAI 2023)

  28. 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)

    2022

  29. Algorithms with Prediction Portfolios
    with: Michael Dinitz, Sungjin Im, Thomas Lavastida, and Sergei Vassilvitskii
    Neural Information Processing Systems (NeurIPS 2022)

  30. Online Scheduling of Parallelizable jobs in the Directed Acyclic Graphs and Speed-up Curves Models
    with: Ruilong Zhang and Shanjiawen Zhao
    Theoretical Compuer Science

  31. On the Impossibility of Decomposing Binary Matroids    
    with: Marilena Leichter and Kirk Pruhs
    Operations Research Letters (ORL)


  32. 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)


  33. Learning-Augmented Algorithms for Online Steiner Tree
    with: Chenyang Xu
    AAAI Confernce on Artificial Intelligence (AAAI 2022)

  34. 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)

    2021

  35. 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.

  36. Robust Online Correlation Clustering
    with: Silvio Lattanzi, Sergei Vassilvitskii, Yuyan Wang, and Rudy Zhou
    Neural Information Processing Systems (NeurIPS 2021)

  37. 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)

  38. An Efficient Reduction of a Gammoid to a Partition Matroid
    with: Marilena Leichter and Kirk Pruhs
    European Symposium on Algorithms (ESA 2021)

  39. 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)

  40. Structural Iterative Rounding for Generalized k-Median Problems
    with: Anupam Gupta and Rudy Zhou
    International Colloquium on Automata, Languages, and Programming (ICALP 2021)

  41. Relational Algorithms for k-means Clustering
    with: Kirk Pruhs, Alireza Samadian and Yuyan Wang
    International Colloquium on Automata, Languages, and Programming (ICALP 2021)

  42. 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)


  43. The Efficiency-Fairness Balance of Round Robin Scheduling  
    with: Shai Vardi
    Operations Research Letters (ORL)


  44. 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)

  45. Scaling Average-Linkage via Sparse Cluster Embeddings
    with: Kefu Lu, Thomas Lavastida, and Yuyan Wang
    Asian Conference on Machine Learning (ACML 2021)

  46. Using Predicted Weights for Ad Delivery
    with: Thomas Lavastida, R. Ravi and Chenyang Xu
    SIAM Conference on Applied and Computational Discrete Algorithms (ACDA 2021)

  47. The Matroid Cup Game
    with: Sungjin Im and Rudy Zhou
    Operations Research Letters (ORL)


  48. The Matroid Intersection Cover Problem
    with: Sungjin Im and Kirk Pruhs
    Operations Research Letters (ORL)


  49. 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)


  50. 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)


  51. 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)


  52. 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)


    2020


  53. 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)


  54. 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)


  55. 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)


  56. 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)

  57. 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)

  58. 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)

  59. 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)


  60. Scheduling for Weighted Flow and Completion Times in Reconfigurable Networks
    with: Michael Dinitz
    IEEE International Conference on Computer Communications (INFOCOM 2020)


  61. 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)

  62. Online Scheduling via Learned Weights
    with: Silvio Lattanzi, Thomas Lavastida, and Sergei Vassilvitskii
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2020)

  63. 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).


    2019


  64. 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)


  65. Cost Effective Active Search
    with: Shali Jiang and Roman Garnett
    Advances in Neural Information Processing Systems (NuerIPS 2019)

  66. 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

  67. Submodular Optimization with Contention Resolution Extensions
    with: Maxim Sviridenko
    International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2019)


  68. A Framework for Parallelizing Hierarchical Clustering Methods
    with: Silvio Lattanzi, Thomas Lavastida, and Kefu Lu
    European Conference on Machine Learning (ECML 2019)


  69. Scheduling to Approximate Minimization Objectives on Identical Machines
    with:
    International Colloquium on Automata, Languages, and Programming (ICALP 2019)


  70. Matroid Coflow Scheduling
    with: Sungjin Im, Kirk Pruhs and Manish Purohit
    International Colloquium on Automata, Languages, and Programming (ICALP 2019)


  71. 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)


  72. 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)


    2018


  73. Efficient Nonmyopic Batch Active Search
    with: Shali Jiang, Gustavo Malkomes, Matthew Abbott, and Roman Garnett
    Advances in Neural Information Processing Systems (NIPS 2018)
    Spotlight Presentation.

  74. 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)

  75. 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)


  76. Scheduling Parallelizable Jobs Online to Maximize Throughput
    with: Kefu Lu, Kunal Agrawal, and Jing Li
    Latin American Theoretical Informatics (LATIN 2018)


    2017


  77. 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.


  78. 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)


  79. 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)


  80. Efficient Nonmyopic Active Search
    with: Shali Jiang, Gustavo Malkomes, Geoff Converse, Alyssa Shofner, and Roman Garnett
    International Conference on Machine Learning (ICML 2017)


  81. 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


  82. Efficient Massively Parallel Methods for Dynamic Programming
    with: Sungjin Im and Xiaorui Sun
    Symposium on Theory of Computing (STOC 2017)


  83. 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)


  84. 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)


  85. 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)


  86. 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.

  87. Fair Scheduling via Iterative Quasi-Uniform Sampling
    with: Sungjin Im
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2017)


    2016


  88. A Competitive Flow Time Algorithm for Heterogeneous Clusters under Polytope Constraints
    with: Sungjin Im, Janardhan Kulkarni, and Kamesh Munagala
    International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2016)


  89. General Profit Scheduling and the Power of Migration on Heterogeneous Machines
    with: Sungjin Im
    ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2016)


  90. 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)


  91. Partitioned Feasibility Tests for Sporadic Tasks on Heterogeneous Machines
    with: Shaurya Ahuja and Kefu Lu
    IEEE International Parallel & Distributed Processing Symposium (IPDPS 2016)


  92. 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)


    2015


  93. 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)


  94. Scheduling Parallel Jobs Online with Convex and Concave Parallelizability
    with: Roozbeh Ebrahimi and Samuel McCauley
    Workshop on Approximation and Online Algorithms (WAOA 2015)


  95. 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)


  96. Weighted Reordering Buffer Improved via Variants of Knapsack Covering Inequalities
    with: Sungjin Im
    International Colloquium on Automata, Languages, and Programming (ICALP 2015)


  97. 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)


  98. 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)


  99. Scheduling in Bandwidth Constrained Tree Networks
    with: Sungjin Im
    ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2015)


  100. 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


  101. 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)


  102. Stochastic Scheduling of Heavy-tailed Jobs
    with: Sungjin Im and Kirk Pruhs
    Symposium on Theoretical Aspects of Computer Science (STACS 2015)


  103. 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)


    2014


  104. Competitively Scheduling Tasks with Intermediate Parallelizability
    with: Sungjin Im, Kirk Pruhs, Eric Torng
    ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2014)


  105. Scheduling to Minimize Energy and Flow Time in Broadcast Scheduling
    with:
    In Journal of Scheduling.


  106. 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)


  107. 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)


  108. New Approximations for Reordering Buffer Management
    with: Sungjin Im
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2014)


    2013


  109. 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).


  110. 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)


  111. Online Batch Scheduling for Flow Objectives
    with: Sungjin Im
    ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2013) Brief Announcement


  112. 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


  113. 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)


  114. Energy Efficient Scheduling of Parallelizable Jobs
    with: Kyle Fox and Sungjin Im
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2013)


    2012


  115. Shortest-Elapsed-Time-First on a Multiprocessor
    with: Neal Barcelo, Sungjin Im and Kirk Pruhs
    Mediterranean Conference on Algorithms (MedAlg 2012)


  116. Speed Scaling for Total Stretch Plus Energy
    with: Daniel Cole, Sungjin Im and Kirk Pruhs
    Operations Research Letters


  117. Scalable K-Means++
    with: Bahman Bahmani, Andrea Vattani, Ravi Kumar and Sergei Vassilvitskii
    International Conference on Very Large Data Bases (VLDB 2012)


  118. Handling Forecast Errors while Bidding for Display Advertising
    with: Kevin Lang and Sergei Vassilvitskii
    International Conference on World Wide Web (WWW 2012)


  119. Online Scheduling with General Cost Functions
    with: Sungjin Im and Kirk Pruhs
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2012)


  120. 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)


    2011


  121. 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)


  122. Fast Clustering using MapReduce
    with: Alina Ene and Sungjin Im
    ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 2011) Oral Presentation.


  123. 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)


  124. 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)


  125. Online Scheduling on Identical Machines using SRPT
    with: Kyle Fox
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2011)


  126. 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)


  127. 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)


    2010


  128. 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)


  129. 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)


  130. 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


    2009


  131. 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


  132. Longest Wait First For Broadcast Scheduling
    with: Chandra Chekuri and Sungjin Im
    Workshop on Approximation and Online Algorithms (WAOA 2009)


  133. Online Scheduling to Minimize the Maximum Delay Factor
    with: Chandra Chekuri
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2009)