Sungjin Im

    Associate Professor
    Electrical Engineering and Computer Science
    Science and Engineering 2 #214
    University of California at Merced
    Merced, CA 95344
    Email: sim3 at ucmerced dot edu
    Phone: 209-228-2358

Research Interests

My area of expertise lies in the design and analysis of algorithms, along with their various applications. My current research focuses on two main areas. Firstly, I'm interested in strengthening traditional worst-case algorithms by incorporating machine learning predictions. This involves exploring how machine learning can improve the performance of algorithms in situations where the worst-case scenario might not be the most common. Secondly, I'm passionate about developing meta-algorithms that can be easily adapted to solve a wide range of problems. This research has a particular emphasis on scheduling and resource allocation. In addition to these current interests, I also maintain a strong interest in database theory and the development of big data algorithms, particularly those that leverage massively parallel processing. Overall, I'm driven by a passion for tackling fundamental algorithmic problems. My research encompasses a broad spectrum of areas, including approximation algorithms, online algorithms, combinatorial optimization, scheduling algorithms, game theory, machine learning, and database theory.

Professional Activities

Teaching

Advising/supervising

Education and Employment:

Honors & Awards (selected):

Publications:

* Copyright: Most of the following papers are published, and the copyright has been tranferred to the respective publishers.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  62. Competitive Flow Time Algorithms for Polyhedral Scheduling
    with Jnardhan Kulkarni and Kamesh Munagala
    FOCS '15

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Funding:

I'm very grateful to the NSF and ONR for the following grants:

Personal: