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.

Remarks

General

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:

• Google Scholar
• Mendeley
• DBLP

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.

References

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

• Style - Lessons in Clarity and Grace
  University Library Signature: DLW1336
• Elements of Style
  Free Online Version available here
  University Library Signature: DLY1271
• Grammatically Correct
  University Library Signature: ENI2642
• Three Sins of Authors in Computer Science and Math

---

Topics

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.

Literature:

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.

Literature:

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.

Literature:

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.

Literature:

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.

Literature:

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.

Literature:

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.

Literature:

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.

Literature:

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 ).

Literature:

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.

Literature:

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).

Literature:

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.

Literature:

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.

Literature:
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.

Literature:
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.

Literature:
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.

Literature:

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.

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

Advisor: Marten Maack

 

 

---

Submission of your Seminar Thesis