Ratio Bound inférieur sur la planification de la machine $ M $

Question

Étant donné une séquence de réels positifs $ a_1, a_2, dots, a_n $ et un entier $ m $, pour chaque $ j $ attribuer $ a_j $ à une machine $ i $, 1 $ <i <m $, afin de minimiser les minimités le maximum, plus de $ i $, de la somme de tous les réels attribués à la machine $ i $.

Théorème: Il n'y a pas d'algorithme de planification Randomisé M $ M $ avec un ratio compétitif inférieur à 4 $ / 3 $ pour tout $ m geq 2 $.

Ce qui suit est l'esquisse de preuve donnée dans le journal:

Considérez les séquences de travail $ m Times 1 $ et $ m Times 1, 2 $. (Ici $ m Times 1 $ désigne une séquence de $ M 1 $.) Si l'algorithme planifie les $ 1 $ M $ sur des machines différentes avec probabilité $ P $, le ratio le pire des cas entre son coût et l'optimal Le coût est au moins $ max {2 - p, 1 + p / 2 } sim 4/3 $.

J'ai un problème à comprendre la preuve. J'apprécierais vraiment si quelqu'un peut expliquer la preuve en détail, surtout comment arriver au ratio le pire des cas de $ max {2-p, 1 + p / 2 } $.