3 papers
cs.DS2022
Online Unrelated-Machine Load Balancing and Generalized Flow with Recourse
Ravishankar Krishnaswamy, Shi Li, Varun Suriyanarayana
We consider the online unrelated-machine load balancing problem with recourse, where the algorithm is allowed to re-assign prior jobs. We give a -competitive algorithm for t…
cs.DS2022
Improved Approximations for Unrelated Machine Scheduling
Sungjin Im, Shi Li
We revisit two well-studied scheduling problems in the unrelated machines setting where each job can have a different processing time on each machine. For minimizing total weighted…
cs.DS2021
Nearly-Linear Time LP Solvers and Rounding Algorithms for Scheduling Problems
Shi Li
We study nearly-linear time approximation algorithms for non-preemptive scheduling problems in two settings: the unrelated machine setting, and the identical machine with job prece…