Sungjin Im

Ravi Kumar

Manish Purohit

ACM Trans. Parallel Comput., December, 2023

Massively Parallel Computation: Algorithms and Applications.

[BibT_eX]

[DOI]

Found. Trends Optim., 2023

Polynomial Time Convergence of the Iterative Evaluation of Datalogo Programs.

[BibT_eX]

[DOI]

CoRR, 2023

On the Convergence Rate of Linear Datalogo over Stable Semirings.

[BibT_eX]

[DOI]

CoRR, 2023

Improved Approximations for Unrelated Machine Scheduling.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Online State Exploration: Competitive Worst Case and Learning-Augmented Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Machine Learning and Knowledge Discovery in Databases: Research Track, 2023

Online Learning and Bandits with Queried Hints.

[BibT_eX]

[DOI]

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Online Dynamic Acknowledgement with Learned Predictions.

[BibT_eX]

[DOI]

Proceedings of the IEEE INFOCOM 2023, 2023

Min-Max Submodular Ranking for Multiple Agents.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence, 2023

2022

Optimizing Polymatroid Functions.

[BibT_eX]

[DOI]

CoRR, 2022

Algorithms with Prediction Portfolios.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Non-clairvoyant Scheduling with Predictions.

[BibT_eX]

[DOI]

Proceedings of the International Symposium on Artificial Intelligence and Mathematics 2022 (ISAIM 2022), 2022

Parsimonious Learning-Augmented Caching.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Machine Learning, 2022

2021

The Matroid Cup Game.

[BibT_eX]

[DOI]

Rudy Zhou

Oper. Res. Lett., 2021

The matroid intersection cover problem.

[BibT_eX]

[DOI]

Oper. Res. Lett., 2021

Online Knapsack with Frequency Predictions.

[BibT_eX]

[DOI]

Ravi Kumar

Manish Purohit

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Faster Matchings via Learned Duals.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

An Approximation Algorithm for the Matrix Tree Multiplication Problem.

[BibT_eX]

[DOI]

Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science, 2021

Instance Optimal Join Size Estimation.

[BibT_eX]

[DOI]

Proceedings of the XI Latin and American Algorithms, Graphs and Optimization Symposium, 2021

A Relational Gradient Descent Algorithm For Support Vector Machine Training.

[BibT_eX]

[DOI]

Proceedings of the 2nd Symposium on Algorithmic Principles of Computer Systems, 2021

Approximate Aggregate Queries Under Additive Inequalities.

[BibT_eX]

[DOI]

Proceedings of the 2nd Symposium on Algorithmic Principles of Computer Systems, 2021

2020

Breaking 1 - 1/e Barrier for Nonpreemptive Throughput Maximization.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2020

Fair Scheduling via Iterative Quasi-Uniform Sampling.

[BibT_eX]

[DOI]

SIAM J. Comput., 2020

Hallucination Helps: Energy Efficient Virtual Circuit Routing.

[BibT_eX]

[DOI]

Antonios Antoniadis

Ravishankar Krishnaswamy

SIAM J. Comput., 2020

Dynamic Weighted Fairness with Minimal Disruptions.

[BibT_eX]

[DOI]

Proc. ACM Meas. Anal. Comput. Syst., 2020

Weighted Completion Time Minimization for Unrelated Machines via Iterative Fair Contention Resolution.

[BibT_eX]

[DOI]

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Online Two-Dimensional Load Balancing.

[BibT_eX]

[DOI]

Ilan Reuven Cohen

Debmalya Panigrahi

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

Unconditional Coresets for Regularized Loss Minimization.

[BibT_eX]

[DOI]

Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, 2020

Fast Noise Removal for k-Means Clustering.

[BibT_eX]

[DOI]

Xiaorui Sun

Rudy Zhou

Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, 2020

2019

Tight Bounds for Online Vector Scheduling.

[BibT_eX]

[DOI]

SIAM J. Comput., 2019

On Coresets for Regularized Loss Minimization.

[BibT_eX]

[DOI]

CoRR, 2019

A Conditional Lower Bound on Graph Connectivity in MapReduce.

[BibT_eX]

[DOI]

CoRR, 2019

Non-clairvoyantly Scheduling to Minimize Convex Functions.

[BibT_eX]

[DOI]

Algorithmica, 2019

Fast and Parallelizable Ranking with Outliers from Pairwise Comparisons.

[BibT_eX]

[DOI]

Proceedings of the Machine Learning and Knowledge Discovery in Databases, 2019

Matroid Coflow Scheduling.

[BibT_eX]

[DOI]

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018

Energy efficient scheduling of parallelizable jobs.

[BibT_eX]

[DOI]

Kyle Fox

Theor. Comput. Sci., 2018

Competitive Algorithms from Competitive Equilibria: Non-Clairvoyant Scheduling under Polyhedral Constraints.

[BibT_eX]

[DOI]

Kamesh Munagala

J. ACM, 2018

Online load balancing on related machines.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Online Partial Throughput Maximization for Multidimensional Coflow.

[BibT_eX]

[DOI]

Zizhan Zheng

Proceedings of the 2018 IEEE Conference on Computer Communications, 2018

2017

A Tight Approximation for Co-flow Scheduling for Minimizing Total Weighted Completion Time.

[BibT_eX]

[DOI]

Manish Purohit

CoRR, 2017

Efficient massively parallel methods for dynamic programming.

[BibT_eX]

[DOI]

Xiaorui Sun

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

An O(Log Log m)-Competitive Algorithm for Online Machine Minimization.

[BibT_eX]

[DOI]

Proceedings of the 2017 IEEE Real-Time Systems Symposium, 2017

Breaking 1 - 1/e Barrier for Non-preemptive Throughput Maximization.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2017

Minimizing Maximum Flow Time on Related Machines via Dynamic Posted Pricing.

[BibT_eX]

[DOI]

Proceedings of the 25th Annual European Symposium on Algorithms, 2017

2016

Min-Sum Set Cover and Its Generalizations.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Competitively Scheduling Tasks with Intermediate Parallelizability.

[BibT_eX]

[DOI]

ACM Trans. Parallel Comput., 2016

Minimum Latency Submodular Cover.

[BibT_eX]

[DOI]

Viswanath Nagarajan

Ruben van der Zwaan

ACM Trans. Algorithms, 2016

Minimizing the maximum flow time in batch scheduling.

[BibT_eX]

[DOI]

Hoon Oh

Oper. Res. Lett., 2016

Brief Announcement: A QPTAS for Non-preemptive Speed-scaling.

[BibT_eX]

[DOI]

Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, 2016

General Profit Scheduling and the Power of Migration on Heterogeneous Machines.

[BibT_eX]

[DOI]

Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, 2016

Fair Online Scheduling for Selfish Jobs on Heterogeneous Machines.

[BibT_eX]

[DOI]

Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, 2016

Scheduling jobs with non-uniform demands on multiple servers without interruption.

[BibT_eX]

[DOI]

Mina Naghshnejad

Mukesh Singhal

Proceedings of the 35th Annual IEEE International Conference on Computer Communications, 2016

Competitive Analysis of Constrained Queueing Systems.

[BibT_eX]

[DOI]

Kamesh Munagala

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Better Unrelated Machine Scheduling for Weighted Completion Time via Random Offsets from Non-uniform Distributions.

[BibT_eX]

[DOI]

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

A Competitive Flow Time Algorithm for Heterogeneous Clusters Under Polytope Constraints.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2016

2015

Stochastic Scheduling of Heavy-tailed Jobs.

[BibT_eX]

[DOI]

Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 2015

Scheduling in Bandwidth Constrained Tree Networks.

[BibT_eX]

[DOI]

Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, 2015

Brief Announcement: Fast and Better Distributed MapReduce Algorithms for k-Center Clustering.

[BibT_eX]

[DOI]

Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, 2015

Temporal Fairness of Round Robin: Competitive Analysis for Lk-norms of Flow Time.

[BibT_eX]

[DOI]

Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, 2015

New Approximations for Broadcast Scheduling via Variants of α-point Rounding.

[BibT_eX]

[DOI]

Maxim Sviridenko

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

A Dynamic Programming Framework for Non-Preemptive Scheduling Problems on Multiple Machines [Extended Abstract].

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Weighted Reordering Buffer Improved via Variants of Knapsack Covering Inequalities.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

On the Randomized Competitive Ratio of Reordering Buffer Management with Non-Uniform Costs.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Competitive Flow Time Algorithms for Polyhedral Scheduling.

[BibT_eX]

[DOI]

Kamesh Munagala

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014

Online Scheduling with General Cost Functions.

[BibT_eX]

[DOI]

SIAM J. Comput., 2014

Preemptive and non-preemptive generalized min sum set cover.

[BibT_eX]

[DOI]

Maxim Sviridenko

Ruben van der Zwaan

Math. Program., 2014

New Approximations for Reordering Buffer Management.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Coordination mechanisms from (almost) all scheduling policies.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Theoretical Computer Science, 2014

SelfishMigrate: A Scalable Algorithm for Non-clairvoyantly Scheduling Heterogeneous Processors.

[BibT_eX]

[DOI]

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013

Optimizing Maximum Flow Time and Maximum Throughput in Broadcast Scheduling.

[BibT_eX]

[DOI]

Maxim Sviridenko

CoRR, 2013

Brief announcement: online batch scheduling for flow objectives.

[BibT_eX]

[DOI]

Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures, 2013

Optimized scheduling of multi-IMA partitions with exclusive region for synchronized real-time multi-core systems.

[BibT_eX]

[DOI]

Proceedings of the Design, Automation and Test in Europe, 2013

Online Non-clairvoyant Scheduling to Simultaneously Minimize All Convex Functions.

[BibT_eX]

[DOI]

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

2012

Online scheduling algorithms for average flow time and its variants

[BibT_eX]

[DOI]

PhD thesis, 2012

Online Scheduling to Minimize Maximum Response Time and Maximum Delay Factor.

[BibT_eX]

[DOI]

Theory Comput., 2012

An online scalable algorithm for average flow time in broadcast scheduling.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2012

Speed scaling for stretch plus energy.

[BibT_eX]

[DOI]

Oper. Res. Lett., 2012

Envy-Free Pricing with General Supply Constraints for Unit Demand Consumers.

[BibT_eX]

[DOI]

Pinyan Lu

Yajun Wang

J. Comput. Sci. Technol., 2012

Scheduling heterogeneous processors isn't as easy as you think.

[BibT_eX]

[DOI]

Anupam Gupta

Ravishankar Krishnaswamy

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Shortest-Elapsed-Time-First on a Multiprocessor.

[BibT_eX]

[DOI]

Proceedings of the Design and Analysis of Algorithms, 2012

2011

A tutorial on amortized local competitiveness in online scheduling.

[BibT_eX]

[DOI]

SIGACT News, 2011

Minimum Latency Submodular Cover in Metrics

[BibT_eX]

[DOI]

Viswanath Nagarajan

CoRR, 2011

Secretary Problems: Laminar Matroid and Interval Scheduling.

[BibT_eX]

[DOI]

Yajun Wang

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Online Scalable Algorithm for Minimizing ℓk-norms of Weighted Flow Time On Unrelated Machines.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Online Scalable Scheduling for the ℓk-norms of Flow Time Without Conservation of Work.

[BibT_eX]

[DOI]

Jeff Edmonds

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Fast clustering using MapReduce.

[BibT_eX]

[DOI]

Alina Ene

Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2011

Signature Pattern Covering via Local Greedy Algorithm and Pattern Shrink.

[BibT_eX]

[DOI]

Proceedings of the 11th IEEE International Conference on Data Mining, 2011

2010

Envy-Free Pricing with General Supply Constraints.

[BibT_eX]

[DOI]

Richard Matthew McCutchen

Pinyan Lu

Yajun Wang

Proceedings of the Internet and Network Economics - 6th International Workshop, 2010

New Models and Algorithms for Throughput Maximization in Broadcast Scheduling - (Extended Abstract).

[BibT_eX]

[DOI]

Louiqa Raschid

Proceedings of the Approximation and Online Algorithms - 8th International Workshop, 2010

Scheduling jobs with varying parallelizability to reduce variance.

[BibT_eX]

[DOI]

Anupam Gupta

Ravishankar Krishnaswamy

Proceedings of the SPAA 2010: Proceedings of the 22nd Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2010

2009

Longest Wait First for Broadcast Scheduling

[BibT_eX]

[DOI]

CoRR, 2009

Longest Wait First for Broadcast Scheduling [Extended Abstract].

[BibT_eX]

[DOI]

Proceedings of the Approximation and Online Algorithms, 7th International Workshop, 2009

Minimizing Maximum Response Time and Delay Factor in Broadcast Scheduling.

[BibT_eX]

[DOI]