BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//hacksw/handcal//NONSGML v1.0//EN
BEGIN:VEVENT
UID:node-3092444@mathematics.huji.ac.il
DTSTAMP:20220519T100000Z
DTSTART:20220519T100000Z
DTEND:20220519T110000Z
SUMMARY:Probability Seminar
DESCRIPTION:**Consider a process in which m tasks are assigned one by one, each to one of \nn servers, positioned at the vertices of an n vertex, d(n)-regular graph \nG=(V,E).\nWhenever a task arrives, a random edge (v,u) in E is selected and an overseer \nis allowed to assign the task either to u or v. The load of every server is \nthe number of tasks assigned to it.\nThe purpose of the overseer is to reduce the maximum load to be as close as \npossible to the average load m/n. We call the difference between these \nnumbers gap(m).\nIn the case G=K_n classical "power of two choices" results show that the \ngreedy algorithm obtains an optimal gap(m) of \theta(log log m).\nLater results by Peres, Talwar and Wieder, show that, on expanders, the \ngreedy algorithm obtains an optimal gap(m) of \theta(log m). It is \nconjectured that this result holds for a much wider class of highly connected \ngraphs. However, on general d connected graphs, such as the cycle graph, the \ngreedy algorithm appears to perform poorly.\nIn a recent work with...
LOCATION:The link will be sent to you after registration
END:VEVENT
END:VCALENDAR