BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION:Lecture - 14:15 Tobias Friedrich - HPI\, Universität Potsdam
Distributed Processes on Scale-Free Networks Abstract: The node degrees of
large real-world networks often follow a power-law distribution. Such scale
-free networks can be social networks\, internet topologies\, the web graph
\, power grids\, or many other networks from literally hundreds of domains.
The talk will introduce three mathematical models of scale-free networks (
preferential attachment graphs\, Chung-Lu graphs\, hyperbolic random graphs
) and analyze some of their properties. We then study three distributed pro
cesses and algorithms on these network models (rumor spreading\, load balan
cing\, de-anonymization) and present several open problems. The talk assume
s no prior knowledge about scale-free networks or distributed computing.
Colloquium - 16:00 Fidaa Abed - Technische Universität Berlin Optimal Coo
rdination Mechanisms for Multi-Job Scheduling Games Abstract: We consider t
he unrelated machine scheduling game in which players control subsets of jo
bs. Each player's objective is to minimize the weighted sum of completion t
ime of her jobs\, while the social cost is the sum of players' costs. The g
oal is to design simple processing policies in the machines with small coor
dination ratio\, i.e.\, the implied equilibria are within a small factor of
the optimal schedule. We work with a weaker equilibrium concept that inclu
des that of Nash. We first prove that if machines order jobs according to t
heir processing time to weight ratio\, a.k.a. Smith-rule\, then the coordin
ation ratio is at most 4\, moreover this is best possible among nonpreempti
ve policies. Then we establish our main result. We design a preemptive poli
cy\, externality\, that extends Smith-rule by adding extra delays on the jo
bs accounting for the negative externality they impose on other players.. F
or this policy we prove that the coordination ratio is 1+ φ ≈ 2.618\, and c
omplement this result by proving that this ratio is best possible even if w
e allow for randomization or full information. Finally\, we establish that
this externality policy induces a potential game and that an ε-equilibrium
can be found in polynomial time. An interesting consequence of our results
is that an ε-local optima of $R|\\,|\sum w_jC_j$ for the jump (a.k.a. move)
neighborhood can be found in polynomial time and are within a factor of 2.
618 of the optimal solution. The latter constitutes the first direct applic
ation of purely game-theoretic ideas to the analysis of a well studied loca
l search heuristic.
DTSTAMP:20150508T170200
DTSTART:20150511T141500
CLASS:PUBLIC
LOCATION:@TU MA 041
SEQUENCE:0
SUMMARY:Distributed Processes on Scale-Free Networks -- Tobias Friedrich
UID:50648555@/www.mi.fu-berlin.de
URL:https://www.mi.fu-berlin.de/en/math/groups/discgeom/dates/olderdates/MD
S-Lecture-Friedrich.html
END:VEVENT
END:VCALENDAR