Αγαπητοί Συνάδελφοι, Φοιτητές και Φίλοι,
Ο κος Χρήστος Πελέκης, εκλεγμένος επικ. καθηγητής του Τμήματος, στον Τομέα Στατιστικής και Επιχ. Έρευνας, θα δώσει διάλεξη την Τρίτη 10/1/2023, 1-2μμ, στην αίθουσα Μ2, με τίτλο:
“A note on the network coloring game: A randomized distributed (Δ+1)-coloring algorithm”
Abstract: The network coloring game has been proposed in the literature
of social sciences as a model for conflict-resolution circumstances. The
players of the game are the vertices of a graph with n vertices and maximum
degree Δ. The game is played over rounds, and in each round all players
simultaneously choose a color from a set of available colors. Players have
local information about the graph: they only observe the colors chosen by
their neighbors and do not communicate or cooperate with one another. A
player is happy when she has chosen a color that is different from the
colors chosen by her neighbors, otherwise she is unhappy, and a
configuration of colors for which all players are happy is a proper
coloring of the graph. It has been shown in the literature that, when the
players adopt a particular greedy randomized strategy, the game reaches a
proper coloring of the graph within O(log n) rounds, with high probability,
provided the number of colors available to each player is at least Δ+2. In
this talk I will show that a modification of the aforementioned greedy
strategy yields likewise a proper coloring of the graph, provided the
number of colors available to each player is at least Δ+1.
This is joint work with Nikolaos Fryganiotis and Symeon Papavassiliou.
Καλείσθε να παρευρεθείτε.