Publications

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.

Foundations of Machine Learning60 papers

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 Allocation78 papers

No, Cake Cutting Really is a Piece of Cake 
with:Stephen Arndt, Sungjin Im, and Kirk Pruhs
ACM-SIAM Symposium on Discrete Algorithms (SODA 2027)
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)
Awarded FOCS Best Paper
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 Computing5 papers

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 Advertising2 papers

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)