[Facets-of-complexity] Invitation to Monday's Lecture & Colloquium Jan.31 - online via Zoom.

["I.Brunke" <i.brunke@fu-berlin.de>]

Dear all,

next Monday's Lecture and Colloquium will take place online via Zoom on January 31.

Please find link to Zoom Meeting here:

https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09

A password is not required!

You all are cordially invited!

Location:

Online via Zoom.

Monday's Lecture: George Mertzios (Durham University)

Time: Monday, January 31 - 14:15 h

Title: Algorithmic Problems on Temporal Graphs

Abstract:

A temporal graph is a graph whose edge set changes over a sequence of discrete time steps. This can be viewed as a discrete sequence G_1, G_2, ... of static graphs, each with a fixed vertex set V. Research in this area is motivated by the fact that many modern systems are highly dynamic and relations (edges) between objects (vertices) vary with time. Although static graphs have been extensively studied for decades from an algorithmic point of view, we are still far from having a concrete set of structural and algorithmic principles for temporal graphs. Many notions and algorithms from the static case can be naturally transferred in a meaningful way to their temporal counterpart, while in other cases new approaches are needed to define the appropriate temporal notions. In particular, some problems become radically different, and often substantially more difficult, when the time dimension is additionally taken into account. In this talk we will discuss some natural but only recently introduced temporal problems and some algorithmic approaches to them.


Break

Monday's Colloquium: Klaus Heeger (Technische Universität Berlin)

Time: Monday, January 31 - 16:00 h s.t.

Title: Stable Matchings Beyond Stable Marriage

Abstract:

Stable matchings are well-studied from computer science, mathematics, and economics. In the most basic setting, called Stable Marriage, there are two sets of agents. Each agent from one set has preferences over the agents from the other set. A matching assigns the agents into groups of two agents. A matching is called stable if there are no two agents preferring each other to the partners assigned to them. In this talk, we will review important parts of my forthcoming PhD thesis concerning the computational complexity of two extensions of this basic model: First, we assume that an instance of Stable Marriage is given, and the aim is to modify the instance (using as few "modifications" as possible) such that a given edge is part of some stable matching. Second, we assume that agents have preferences over sets of d-1 other agents (for some d>2). In this case, a matching matches agents into groups of size d, and a matching is stable if there are no d agents preferring to be matched together to being unmatched. While since 1991 this problem is known to be NP-complete, we study the case that the preferences of all agents are "similar".

You all are cordially invited!

-- 

Virenfrei. www.avast.com