I shall also talk about two models of multiprocessor scheduling with rejection. The first is the model of Bartal, Leonardi, Marchetti-Spaccamela, Sgall and Stougie. I have developed two randomized algorithms for this model. The first algorithm performs well for small m, achieving competitive ratios of 3/2, 1.83579, 2.05441 for m = 2,3,4, respectively. The second algorithm outperforms the first for m > 5. It beats the deterministic algorithm of Bartal et al. for all m = 5, ... 1000. I am currently developing a proof that this is true for all m. The second model differs in that preemption is allowed. For this model, I have developed a deterministic algorithm which is 2.38743-competitive for all m. I have also developed randomized algorithms which outperform the best deterministic algorithms for small m. In this talk, I shall explain my non-preemptive algorithm for small m, and outline its analysis.
(Practice job interview talk.)