2 papers
cs.DS2020
Weighted Completion Time Minimization for Unrelated Machines via Iterative Fair Contention Resolution
Sungjin Im, Maryam Shadloo
We give a 1.488-approximation for the classic scheduling problem of minimizing total weighted completion time on unrelated machines. This is a considerable improvement on the recen…
cs.DS2017
Online Load Balancing for Related Machines
Sungjin Im, Nathaniel Kell, Debmalya Panigrahi +1
In the load balancing problem, introduced by Graham in the 1960s (SIAM J. of Appl. Math. 1966, 1969), jobs arriving online have to be assigned to machines so to minimize an objecti…