BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION:  Lecture - 14:15     Tobias Friedrich -  HPI\, Universität Pot
 sdam     Distributed Processes on Scale-Free Networks    Abstract:   The no
 de degrees of large real-world networks often follow a power-law distributi
 on. Such scale-free networks can be social networks\, internet topologies\,
  the web graph\, power grids\, or many other networks from literally hundre
 ds of domains. The talk will introduce three mathematical models of scale-f
 ree networks (preferential attachment graphs\, Chung-Lu graphs\, hyperbolic
  random graphs) and analyze some of their properties. We then study three d
 istributed processes and algorithms on these network models (rumor spreadin
 g\, load balancing\, de-anonymization) and present several open problems. T
 he talk assumes no prior knowledge about scale-free networks or distributed
  computing.         Colloquium - 16:00     Fidaa Abed -  Technische Univers
 ität Berlin     Optimal Coordination Mechanisms for Multi-Job Scheduling Ga
 mes    Abstract:   We consider the unrelated machine scheduling game in whi
 ch players control subsets of jobs. Each player's objective is to minimize 
 the weighted sum of completion time of her jobs\, while the social cost is 
 the sum of players' costs. The goal is to design simple processing policies
  in the machines with small coordination ratio\, i.e.\, the implied equilib
 ria are within a small factor of the optimal schedule. We work with a weake
 r equilibrium concept that includes that of Nash.  We first prove that if m
 achines order jobs according to their processing time to weight ratio\, a.k
 .a. Smith-rule\, then the coordination ratio is at most 4\, moreover this i
 s best possible among nonpreemptive policies. Then we establish our main re
 sult. We design a preemptive policy\,  externality \, that extends Smith-ru
 le by adding extra delays on the jobs accounting for the negative externali
 ty they impose on other players.. For this policy we prove that the coordin
 ation ratio is 1+ φ ≈ 2.618\, and complement this result by proving that th
 is ratio is best possible even if we allow for randomization or full inform
 ation. Finally\, we establish that this externality policy induces a potent
 ial game and that an ε-equilibrium can be found in polynomial time. An inte
 resting 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 application of purely game-theoretic ideas to 
 the analysis of a well studied local 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