An improved monotone algorithm for scheduling related machines with precedence constraints

We answer an open question posed by Krumke et al. (2008) by showing how to turn the algorithm of Chekuri and Bender for scheduling related machines with precedence constraints into an O(log m)-approximation algorithm that is monotone in expectation. This significantly improves on the previously best known monotone approximation algorithms for this problem, from Krumke et al. and Thielen and Krumke (2008), which have an approximation guarantee of O(m^2/3)