Local Algorithms

The central control and optimization of networks reaches its limits if networks become very large and change constantly. Examples of such networks are the Internet, web graphs, peer-to-peer systems or large teams of mobile robots with limited sensor range. Therefore, the nodes themselves have to decide upon their actions, whereby they only possess a limited, local view on the overall network. On the other hand, such local strategies, performed by nodes of the network, should lead to a globally good behavior. In this seminar, local algorithms for various problems are presented and analyzed.


The seminar will take place as a block seminar at the end of the lecture period.



  • Seminar I / Seminar II

Dates & Deadlines

The seminar will take place as a block seminar at the end of the lecture period - we hope that we will be able to meet in person, but if this is not the case, we will probably use BBB.

  • First meeting (distribution of topics):
    Monday, 4.4., 16h (F0.530)
  • Latest period for the initial meeting with your advisor (You are expected to have read the paper, and come with concrete questions):
    25.4. - 27.4.
  • Short Talks (5-10 minute introduction to your topic):
    Tuesday, 3.5., 9-12h (FU.511)
  • Submission deadline of the 0-version of seminar thesis (see Step II below):
    Monday, 6.6., 11:59pm
    (We strongly recommend to give at least part of the thesis to your advisor in advance to this deadline, in consultation with him)
  • Submission deadline of the reviews (see Step III below):
    Friday, 17.6., 11:59pm
  • Start test presentations (see Step IV below):
    27.6. - 29.6.
  • Submission deadline of the final version of the seminar thesis:
    Sunday, 3.7., 11:59pm
  • Block Seminar, Presentation of your work (see Step I below):
    Tuesday, 5.7., and Wednesday, 6.7. (time and room tba)

Topics and Registrations

The topics (see below) are given in the first meeting. Reservations or defaults of issues are not possible. You should have a look at the topics (see below) and respective papers before the first meeting and make your mind up about your topic preferences. The application for this Seminar is managed through the Jupyter System. Klick here for more information on the application procedure.

Grading and Demands

I) Presentation

45 minutes presentation.
15 minutes discussion and questions.
Your audience: Your fellow students.
As a minimal requirement, the presentation should motivate your model, formally introduce the problem, explain the necessary techniques, and provide insight into the necessary algorithms and their analysis (i.e., with proofs!). Some ideas e.g. "Scientific Working"

II) Seminar thesis

Essay of length 12 to 20 pages written according to the standards of a scientific paper. Submitting work of others is cheating and a violation of academic plagiarism rules, which is a serious offense. We use a commercial, Internet-based plagiarism detection service to check your submissions. Also the simple copying of the original work into the own thesis causes the failure of the seminar.

Note that the 0-version of your thesis should be as closely to your final thesis as possible. In particular, it should be complete content-wise (the minimum number of pages also applies to the 0-version).

III) Reviews

  • Peer review procedure similar to scientific publications
  • You submit your thesis (paper) at easychair.org
  • Some (2) peers (other students) review your submission
    • Read and understand the submitted paper
    • Criticize your paper
    • Make recommendations on how to improve
    • Be honest, polite, and helpful when writing your reviews
  • The reviews you write will influence your final grade
  • The reviews you receive will not influence (but your final version)
  • Each student has to write 2 reviews (each 1-2 pages)

IV) Test run of your presentation

  • Do a test run with your presentation.
  • Meet in groups of approx. 3-4 students
  • Give each other feedback
  • Negotiate date yourselves
  • We can organize a room for you if necessary

We expect your active participation (as opposed to mere attendance) at all presentations of this seminar.

We will grade the quality of the presentation and the quality of the essay / seminar thesis individually. You have to pass (i.e., 4.0 or better) each part individually to pass this course. Note that commitment, diligence, and compliance with our deadlines will be taken into account.



Each topic has one or several references that should be understood as starting points for your research. Hence, it is very likely that you will need further papers or textbooks to fully understand your topic. The actual content of your seminar thesis as well as your seminar talk should be discussed with your adviser.
It is your responsibility to contact your adviser and schedule appointments with them early enough. We strongly recommend you to discuss questions regarding the topic, the composition, and the structure of your written seminar thesis with your adviser. The same holds for your seminar talk. Note that finding an appointment directly before your thesis' submission or seminar talk cannot be guaranteed, since the advisers need to arrange their appointments with their own teaching and research.
If you are looking for additional research papers, the following links might be helpful:

Seminar Thesis

We expect an essay of length 12 to 20 pages written according to the standards of a scientific paper. A simple summary of the referenced literature is insufficient. We expect you to identify the important ideas and proofs of the referenced literature and present them in a correct and appropriate way. The mandatory typesetting for your thesis is LaTeX (see below for details). All citations must be marked as such and referenced with their origin. Plagiarism directly leads to failure of the seminar. Note that plagiarism not only includes copies from the original literature, but also copies from other authors (e.g., other seminar theses) or translations of them.

Title and Abstract

Create a brief abstract that summarizes the problem and the main results. An abstract is kept short (typically 10-20 lines). Also make up a title for your thesis (note that this is not necessarily the title of the used literature or the title from our topic list). It is important to make your own reasoning about a title that describes the thesis best from your point of view.


Each thesis contains a reference list that contains at least the literature used in your thesis. In the digital libraries of DBLP, ACM, IEEE, or Springer you can find detailed literature reference information. For conferencing proceedings or journals ALWAYS specify the pages. For journals, additionally provide volume and journal number. Do not rely on the authors to do their references correct (e.g., reference list in a paper or at the author's website). Sometimes this references are wrong or incomplete. Also do not rely on search engines like CiteSeer or Google Scholar: always verify the correctness and completeness of your references. Especially, it is insufficient if you only provide links to the papers or citations in the web.

Further Reading

For further reading we advice


Topic 1:   Dynamic Perfect Hashing

The dynamic dictionary problem is considered: provide an algorithm for storing a dynamic set, allowing the operations insert, delete, and lookup. A dynamic perfect hashing strategy is given: a randomized algorithm for the dynamic dictionary problem that takes O(1) worst-case time for lookups and O(1) amortized expected time for insertions and deletions; it uses space proportional to the size of the set stored. Furthermore, lower bounds for the time complexity of a class of deterministic algorithms for the dictionary problem are proved.


M. Dietzfelbinger, A. Karlin, K. Mehlhorn, F. Meyer auf der Heide, H. Rohnert, R. Tarjan: Dynamic Perfect Hashing: Upper and Lower Bounds. Siam J. Comput., Vol. 23, No. 4, pp. 738-761 (1994)

Advisor: Friedhelm Meyer auf der Heide


Topic 2:   Dynamic Hashing in Real Time

A dynamic hashing scheme that performs in real time is presented. It uses linear space and needs worst case constant time per instruction. Thus instructions can be given in constant length time intervals. Answers to queries given by the algorithm are always correct, the space bound is always satisfied. The algorithm is of the Monte Carlo type; it fails to meet the real time assumption only with very small probability. The construction is based on a new high performance universal class of hash functions.


M. Dietzfelbinger, F. Meyer auf der Heide: Dynamic Hashing in Real Time. In Informatik, Teubner, Leipzig 1992

Advisor: Friedhelm Meyer auf der Heide


Topic 3:   A 12/7-approximation algorithm for the discrete Bamboo Garden Trimming problem

The author presents a new algorithm for the so-called Bamboo Garden Trimming problem. In this problem there is a finite number of given bamboo plants each with an individual growth rate. Each day one of the plants can be cut down, i.e., its height set to zero, and the goal is to find a strategy to minimize the maximum height in the garden. The problem can also be formulated as a maintenance problem for machines. In the paper, a new 12/7-approximation algorithm is presented that is based on algorithms for the so-called Pinwheel Scheduling problem.


Martijn van Ee: A 12/7-approximation algorithm for the discrete Bamboo Garden Trimming problem. Oper. Res. Lett. 49(5): 645-649 (2021)

Advisor: Marten Maack


Topic 4:   A local-ratio theorem for approximating the weighted vertex cover problem

The local ratio technique is a methodology for the design and analysis of algorithms for a broad range of optimization problems. The technique is remarkably simple and elegant, and yet can be applied to several classical and fundamental problems (including covering problems, packing problems, and scheduling problems). The local ratio technique uses elementary math and requires combinatorial insight into the structure and properties of the problem at hand. Typically, when using the technique, one has to invent a weight function for a problem instance under which every “reasonable” solution is “good”. The local ratio technique is closely related to the primal-dual schema, though it is not based on weak LP duality (which is the basis of the primal-dual approach) since it is not based on linear programming.


  1. Bar-Yehuda, and Even. A local-ratio theorm for approximating the weighted vertex cover problem. No. CS Technion report CS0260. Computer Science Department, Technion, 1983
  2. Bar-Yehuda, Bendel, Freund, & Rawitz. Local ratio: A unified framework for approximation algorithms. in memoriam: Shimon even 1935-2004. ACM Computing Surveys (CSUR) 36.4 (2004)

Advisor: Manuel Malatyali


Topic 5:   Analysis of UML Activities Using Dynamic Meta Modeling

Dynamic Meta Modeling (DMM) is a universal approach to defining semantics for languages syntactically grounded on meta models. DMM has been designed with the aim of getting highly understandable yet precise semantic models which in particular allow for a formal analysis. In this paper, we exemplify this by showing how DMM can be used to give a semantics to and define an associated analysis technique for UML Activities.


Gregor Engels, Christian Soltenborn, Heike Wehrheim: Analysis of UML Activities using Dynamic Meta Modeling. FMOODS 2007: 76-90

Advisor: Christian Soltenborn


Topic 6:   Self-Stabilizing Systems in Spite of Distributed Control

In his seminal work, Dijkstra studies the existence of self-stabilizing protocols. In general, distributed systems are error-prone, and the idea of self-stabilizing protocols is that the involved processes react to errors and redirect the system into a legitimate state. Self-Stabilizing protocols fulfill two properties: convergence and closure. Starting in an illegal state, the execution of the protocol leads to a legitimate state in finite time. Moreover, as soon as a legitimate state is reached, the protocol remains in a legitimate state (as long as no further error occurs). The concrete definition of illegal and legitimate states depends on the application. Up to this work, it was unclear whether such protocols may exist in general. Dijkstra answers the question positively by introducing three self-stabilizing protocols for the distributed token ring. In [1] the original paper is contained. Later on, in [2] a proof that the protocols are indeed self-stabilizing is given.


  1. Dijkstra, Edsger W.: Self-stabilizing systems in spite of distributed control. Communications of the ACM 17.11 (1974): pp.643-644
  2. Dijkstra, Edsger W.: A belated proof of self-stabilization. Distributed Computing 1.1 (1986): pp.5-6

Advisor: Jannik Castenow


Topic 7:   Separating Bounded and Unbounded Asynchrony for Autonomous Robots: Point Convergence with Limited Visibility

We consider distributed computations, by identical autonomous mobile entities, that solve the Point Convergence problem: given an arbitrary initial configuration of entities, disposed in the Euclidean plane, move in such a way that, for all ε>0, a configuration is eventually reached and maintained in which the separation between all entities is at most ε. The problem has been previously studied in a variety of settings. Our study concerns the minimal assumptions under which entities, moving asynchronously with limited and unknown visibility range and subject to limited imprecision in measurements, can be guaranteed to converge in this way. We present an algorithm that solves Point Convergence, provided the degree of asynchrony is bounded by some arbitrarily large but fixed constant. This provides a strong positive answer to a decade old open question posed by Katreniak. We also prove that, in an otherwise comparable setting, Point Convergence is impossible with unbounded asynchrony. This serves to distinguish the power of bounded and unbounded asynchrony in the control of autonomous mobile entities, settling at the same time a long-standing question whether in the Euclidean plane synchronous entities are more powerful than asynchronous ones.


Kirkpatrick, David, et al.: Separating Bounded and Unbounded Asynchrony for Autonomous Robots: Point Convergence with Limited Visibility. Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing. 2021, pp. 9-19

Advisor: Jannik Castenow


Topic 8:   Entropy Search for Information-Efficient Global Optimization

Contemporary global optimization algorithms are based on local measures of utility, rather than a probability measure over location and value of the optimum. They thus attempt to collect low function values, not to learn about the optimum. The reason for the absence of probabilistic global optimizers is that the corresponding inference problem is intractable in several ways. This paper develops desiderata for probabilistic optimization algorithms, then presents a concrete algorithm which addresses each of the computational intractabilities with a sequence of approximations and explicitly addresses the decision problem of maximizing information gain from each evaluation.


P. Hennig, C. J. Schuler: Entropy Search for Information-Efficient Global Optimization. Journal of Machine Learning Research 13, no. 57, 2012, pp. 1809–1837

Advisor: Jonas Hanselle


Topic 9:   Time-Optimal Gathering under Limited Visibility with One-Axis Agreement

We consider the distributed setting of N autonomous mobile robots that operate in Look-Compute-Move (LCM) cycles following the well-celebrated classic oblivious robots model. We study the fundamental problem of gathering N autonomous robots on a plane, which requires all robots to meet at a single point (or to position within a small area) that is not known beforehand. We consider limited visibility under which robots are only able to see other robots up to a constant Euclidean distance and focus on the time complexity of gathering by robots under limited visibility. There exists an O( D G ) time algorithm for this problem in the fully synchronous setting, assuming that the robots agree on one coordinate axis (say north), where D G is the diameter of the visibility graph of the initial configuration. In this article, we provide the first O(DE ) time algorithm for this problem in the asynchronous setting under the same assumption of robots’ agreement with one coordinate axis, where D E is the Euclidean distance between farthest-pair of robots in the initial configuration. The runtime of our algorithm is a significant improvement since for any initial configuration of N ≥ 1 robots, DE ≤ DG , and there exist initial configurations for which DG can be quadratic on DE , i.e., DG = Θ (DE 2 ). Moreover, our algorithm is asymptotically time-optimal since the trivial time lower bound for this problem is Ω(DE ).


Pavan Poudel and Gokarna Sharma: Time-Optimal Gathering under Limited Visibility with One-Axis Agreement

Advisor: Jonas Harbig


Topic 10:   Autonomous Mobile Robots: Refining the Computational Landscape

Within distributed computing, the study of distributed systems of identical mobile computational entities, called robots, operating in a Euclidean space is rather extensive. When a robot is activated, it executes a Look-Compute-Move cycle: it takes a snapshot of the environment (Look); with this input, it computes its destination (Compute); and then it moves towards that destination (Move). The choice of the times a robot is activated and how long its cycle lasts is made by a fair (but adversarial) scheduler; three schedulers are usually considered: fully synchronous (Fsync), semi-synchronous (Ssync), and asynchronous (Async).Extensive investigations have been carried out, under all those schedulers, within four models, corresponding to different levels of computational and communication powers of the robots: OBLOT(the weakest), LUMI (the strongest), and two intermediate models FSTA and FCOM. The many results for specific problems have provided insights on the relationships between the models and with respect to the activation schedulers. Recently, a comprehensive characterization of these relationships has been provided with respect to the Fsync and Ssync schedulers; however, in several cases, the results were obtained under some restrictive assumptions (chirality and/or rigidity). In this paper, we improve the characterization by removing those assumptions, providing a refined map of the computational landscape for those robots. We also establish some preliminary results with respect to the Async scheduler.


Buchin, K., Flocchini, P., Kostitsyna, I., Peters, T., Santoro, N., Wada, K: Autonomous Mobile Robots: Refining the Computational Landscape

Advisor: Jonas Harbig


Topic 11:   A Peer-to-Peer Based Cloud Storage Supporting Orthogonal Range Queries of Arbitrary Dimension

Consider the problem of storing and retrieving data in a distributed system. A data-item can be viewed as a point in a multi-dimensional space. Each dimension reflects some attribute of the data (size, creation date, data type, …). In such a system not only the simple search for a single item is important but also how a set of data-items can be accessed. For example, a query might be interested in all data-items where the size is in between 2MB and 10MB and the date of creation was within the last month. In the given paper, the authors explore how a distributed system can be organized such that these multi-dimensional range queries are efficiently processed, while the architecture of the network shall be simple (and as far as possible independent of the used data).


M. Benter, T. Knollmann, F. Meyer auf der Heide, A. Setzer, J. Sundermeier: A Peer-to-Peer Based Cloud Storage Supporting Orthogonal Range Queries of Arbitrary Dimension. ALGOCLOUD 2018, pp. 48-56


Advisor: Till Knollmann


Topic 12:   Impossibility of distributed consensus with one faulty process

The FLP (Fischer, Lynch, Patterson) result was a ground-breaking result regarding the consensus problem in asynchronous systems where a set of participants communicate via messages. In an asynchronous system, the participants do not interact synchronously but each one has its own pace (one participant might be very slow in processing messages, while some other is extremely fast). The goal of the consensus problem is that all participants agree upon a common value in finite time (for example, agree on if a transaction is valid or not). In the given paper, the authors study if achieving a consensus in an asynchronous system is possibly if one of the participants might crash.


M.J. Fischer, N.A. Lynch, M.S. Paterson: Impossibility of Distributed Consensus with One Faulty Process. Journal of the ACM, Volume 32, Issue 2 (April 1985), pp 374–382

Advisor: Till Knollmann


Topic 13:   Scheduling on Two Unbounded Resources with Communication Costs

Heterogeneous computing systems became a popular and powerful platform, containing several heterogeneous computing elements (e.g. CPU+GPU). In this paper, we consider that we have two platforms, each with an unbounded number of processors. We want to execute an application represented as a Directed acyclic Graph (DAG) using these two platforms. Each task of the application has two possible execution times, depending on the platform it is executed on. Also, there is a cost to transfer data from one platform to another between successive tasks. The goal here is to minimize the finish execution time of the last task of the application (usually called makespan). We show that the problem is NP-complete for graphs of depth at least 3 but polynomial for graphs of depth at most 2. Finally, we focus on particular classes of graphs, by providing polynomial-time algorithms for bi-partite graphs, trees and 2-series-parallel graphs with different assumptions on communication delays.

M. Ait Aba, G. Aupy, A. Munier-Kordon: Scheduling on Two Unbounded Resources with Communication Costs. [Research Report] RR-9264, Inria. 2019

Advisor: Simon Pukrop


Topic 14:   A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem

The multiple knapsack problem (MKP) is a natural and well-known generalization of the single knapsack problem and is defined as follows. We are given a set of n items and m bins (knapsacks) such that each item i has a profit p(i) and a size s(i), and each bin j has a capacity c(j). The goal is to find a subset of items of maximum profit such that they have a feasible packing in the bins. MKP is a special case of the generalized assignment problem (GAP) where the profit and the size of an item can vary based on the specific bin that it is assigned to. GAP is APX-hard and a 2-approximation, for it is implicit in the work of Shmoys and Tardos [Math. Program. A, 62 (1993), pp. 461–474], and thus far, this was also the best known approximation for MKP. The main result of this paper is a polynomial time approximation scheme (PTAS) for MKP. Apart from its inherent theoretical interest as a common generalization of the well-studied knapsack and bin packing problems, it appears to be the strongest special case of GAP that is not APX-hard. We substantiate this by showing that slight generalizations of MKP are APX-hard. Thus our results help demarcate the boundary at which instances of GAP become APX-hard. An interesting aspect of our approach is a PTAS-preserving reduction from an arbitrary instance of MKP to an instance with O(log n) distinct sizes and profits

Note from Advisor: The intended main focus of this topic is chapter two of the linked paper.

Chandra Chekuri, Sanjeev Khanna: A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem. 2006 Society for Industrial and Applied Mathematics

Advisor: Simon Pukrop


Topic 15:   Bayesian Optimization with Robust Bayesian Neural Networks

Bayesian optimization is a prominent method for optimizing expensive to evaluate black-box functions that is prominently applied to tuning the hyperparameters of machine learning algorithms. Despite its successes, the prototypical Bayesian optimization approach - using Gaussian process models - does not scale well to either many hyperparameters or many function evaluations. Attacking this lack of scalability and flexibility is thus one of the key challenges of the field. We present a general approach for using flexible parametric models (neural networks) for Bayesian optimization, staying as close to a truly Bayesian treatment as possible. We obtain scalability through stochastic gradient Hamiltonian Monte Carlo, whose robustness we improve via a scale adaptation. Experiments including multi-task Bayesian optimization with 21 tasks, parallel optimization of deep neural networks and deep reinforcement learning show the power and flexibility of this approach.

Springenberg, Jost Tobias, Aaron Klein, Stefan Falkner, and Frank Hutter. 2016. Bayesian Optimization with Robust Bayesian Neural Networks. In Advances in Neural Information Processing Systems. Vol. 29.

Advisor: Jonas Hanselle


Topic 16:   Verification of Workflow Nets

Workflow management systems will change the architecture of future information systems dramatically. The explicit representation of business procedures is one of the main issues when introducing a workflow management system. In this paper we focus on a class of Petri nets suitable for the representation, validation and verification of these procedures. We will show that the correctness of a procedure represented by such a Petri net can be verified by using standard Petri-net-based techniques. Based on this result we provide a comprehensive set of transformation rules which can be used to construct and modify correct procedures.


Wil van der Aalst: Verification of Workflow nets. LNCS, Vol. 1248, 1997, pp. 407-426.

Advisor: Christian Soltenborn


Topic 17:   Improving Online Algorithms via ML Predictions

In online scheduling, scheduling decisions have to be made without full knowledge of the instance, and in the non-clairvoyant setting, in particular, full knowledge about tasks and their processing times is only attained after they have been fully executed. The present paper considers two classical scheduling problems in this setting with an addition – the input includes guesses regarding some of the missing knowledge. These guesses could, for instance, be attained via machine learning. The authors design algorithm that are both consistent, i.e., outperform pure online algorithms if the predictions are good, and robust, i.e., do not perform too badly if the predictions are bad or even adversarial.

Manish Purohit, Zoya Svitkina, Ravi Kumar: Improving Online Algorithms via ML Predictions. NeurIPS 2018: 9684-9693

Advisor: Marten Maack



Submission of your Seminar Thesis

The thesis has to be created with LaTeX using our customized template, which you can download here, or you can clone the git-repository. We will create a complete volume consisting of all submissions. This means that you have to closely follow the instructions below - otherwise, this will result in more work for you as well as for us.

You have to submit the LaTeX sources (your subfolder from the template is enough) AND a complete pdf of your seminar thesis. All files should be contained in only one zip or tar.gz file. Please do NOT include your matriculation number in your thesis.

For the LaTeX document you have to follow the following rules:

  • Each author gets his own prefix. (Example: the author "Matthias Fischer" gets his unique prefix "MaFi". Make sure there are no conflicts with other students.)
  • All your LaTeX files and pictures have to be contained in a single subfolder of the template using your prefix as name.
  • There is only one "*.tex" file for your complete seminar thesis.
  • The name of your LaTeX file consists only of your prefix supplemented by the suffix ".tex" (e.g., "MaFi.tex").
  • You can modify the "SI" folder and "SI.tex" in the template as a starting point.
  • The document must be compiled with pdflatex. Hence, pictures must be included as pdf, jpg or png.
  • To compile the document, you need to include your LaTeX file by adding the command "\includeseminar{...}" to the "main.tex" file in the root folder. (e.g., "\includeseminar{MaFi/MaFi}")
  • Your file must be encoded in UTF-8.
  • Your highest breakdown-level is \section. (Thus, you can use \section, \subsection, \subsubsection, \paragraph, etc.)
  • To distinguish all self-defined commands, labels and references, each author gets his own prefix. (Example: the author "Matthias Fischer" gets his unique prefix "MaFi".)
  • Each command, label and reference consists of the prefix, followed by an individual identifier. Thus, if Matthias wants to call a label "myCoolLabel", the label has to be defined by \label{MaFi:MyCoolLabel}.
  • After the \maketitle call in your LaTeX document, you have to add your abstract with the command "\abstract{ ... }". After the abstract add your local table of contents with the commands "\makeminitoc".
  • We only use the svmult theorem environment. This means, the option "nospthms" and the package "amsthm" can not be used. (The package "amsthm" is not compatible to "svmult".)
  • We do not use the BibTeX compiler to process literature references. Instead of this, you have to add your literature references like presented in the template file "SI.tex". You have to follow the style given in the template file, i.e., "author, title, year,...".
  • To format the pseudocode of your algorithms you can either use algorithmicx together with its floating environment "algorithm" from the package algorithms, or you can use the listings environment. We recommend to start with predefined commands as given by package algpseudocode. We do not use the package "algorithmic".
  • You are not allowed to modify the "main.tex" file (apart from the \includeseminar command) or any other file in the root folder of the template. This also means, that you cannot use any other packages as specified in the main file.