Distributed Algorithms for Optimization Problems

Distributed Algorithms for Optimization Problems

In this proseminar we will take a look into the world of optimization problems from the perspective of distributed algorithms. In an optimization problem, the task is to find an optimal solution (according to some criterion) among a set of feasible solutions. Both in the centralized and the distributed world, optimization problems are often difficult to solve exactly, which is why many algorithms aim for a (not necessarily optimal) solution that at least approximates the optimal solution well in some manner.

The main focus of this seminar will lie on such approximation algorithms for central optimization problems on graphs, such as minimum dominating set or maximum independent set. The main model of computation we will consider is the standard LOCAL model of distributed computation. Note that this is a theory seminar, i.e., we will focus on algorithm analysis, lower bound proofs, and the like.

Each student will be assigned one or two papers, and has to present the assigned paper(s) twice. The first presentation is followed by a group discussion about the presented content as well as a feedback round where suggestions for improvements are made. The second presentation will be given at a later stage and is the part of the proseminar that is mainly responsible for your grade.

The required language for the presentations is English.

If you are interested in this proseminar, please register your interest in the proseminar assignment system.

 

Date, Time, Location

The default weekly slot for the seminar will be Wednesday, 16:00 - 18:00, location TBD. The kick-off meeting will take place on Oct 22, 16:00 - 18:00.

 

Prerequisites

There are no formal prerequisites for this seminar, but a general interest in graph theory and designing/analyzing algorithms as well as a basic understanding of probabilities and algorithmic analysis (e.g., O-notation) will be helpful.