BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: We study the recently proposed Euclidean Generalized Network C
reation Game by Bilò et al.[SPAA 2019] and investigate the creation of (bet
a\,gamma)-networks\, which are in beta-approximate Nash equilibrium and hav
e a total cost of at most gamma times the optimal cost. In our model we hav
e n agents corresponding to points in Euclidean space create costly edges a
mong themselves to optimize their centrality in the created network. Our ma
in result is a simple O(n^2)-time algorithm that computes a (beta\,beta)-ne
twork with low beta for any given set of points. Along the way\, we signifi
cantly improve several results from Bilò et al. and we asymptotically resol
ve a conjecture about the Price of Anarchy.
DTSTAMP:20201208T143600
DTSTART:20201214T160000
CLASS:PUBLIC
LOCATION:online
SEQUENCE:0
SUMMARY:Jannik Peters: Efficiency and Stability in Euclidean Network Desig
n
UID:107739106@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20201214-C-Peters.html
END:VEVENT
END:VCALENDAR