Rapporto più basso con un rapporto competitivo della programmazione di $ m $-machine

Question

Data una sequenza di reali positivi $ a_1, a_2, dots, a_n $ e un intero $ m $, per ogni $ j $ assegna $ a_j $ a una macchina $ i $, $ 1 <i $, in modo da ridurre al minimo Il massimo, oltre $ i $, della somma di tutti i reali assegnati alla macchina $ i $.

Teorema: non esiste un algoritmo randomizzato $ m $ -machine con un rapporto competitivo inferiore a $ 4/3 $ per qualsiasi $ m geq 2 $.

Di seguito è riportato lo schizzo di prova fornito nella carta:

Considera le sequenze di lavoro $ M Times 1 $ e $ M Times 1, 2 $. (Qui $ M Times 1 $ indica una sequenza di $ M $ 1.) Se l'algoritmo pianifica $ M $ 1 su $ M $ diverse macchine con probabilità $ p $, il rapporto peggiore tra il suo costo e l'ottimale Il costo è almeno $ max {2 - p, 1 + p/2 } sim 4/3 $.

Ho problemi a capire la prova. Apprezzerei davvero se qualcuno potesse spiegare la prova in dettaglio, in particolare come arrivare al rapporto peggiore di $ max {2-P, 1+p/2 } $.