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.


    2018


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

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

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


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


    2017


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


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


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


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


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


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


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


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


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


  14. Stochastic Online Scheduling on Unrelated Machines
    with: Varun Gupta, Marc Uetz and Qiaomin Xie
    Conference on Integer Programming and Combinatorial Optimization (IPCO 2017)


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


    2016


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


    2013


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


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


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


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


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


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


    2012


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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



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


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


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


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