Online and Distributed Algorithms
|Responsible||Dr. Lucia Draque Penso|
|Assistant||Dr. Jens Maßberg|
MATH, 4 Hours Course, 2 Hour Exercises (4+2)
A combination with OR-Praktikum is possible.
Please arrange a date with Dr. Maßberg if so.
|Place and Time||Course:|
In this modular master course, we will cover a handful of the nicest algorithms and techniques from the principles of distributed computing by looking at a different theme every class, including many graph and network related topics, such as vertex coloring, dominating set, maximal independent set, diameter and radius, small networks, sorting/counting in networks, searching and routing issues, but now from a distributed point of view instead of a sequential one traditional from optimization.
This master course is self-contained and does not need any class as prior requirement, though those who have already taken graph theory, optimization or game theory may find it particularly interesting. However, the model of computation differs from all those. Though it is distributed, each network graph node being a distinct participant in the algorithm, a solution does not involve an equilibrium such as in game theory, but rather achieves in a distributed manner a specific goal, such as optimizing a parameter or finding a sort of structure.
Due to the distributed computation, besides the time complexity, communication complexity issues such as message complexity will play a role. We will take a look at both deterministic and randomized algorithms, as well as at approximation algorithms for hard problems.