Thesis topics

If not otherwise noted, the topics below can be handed out as either a Bachelor or Master/Diploma thesis (with according modification to length and difficulty). If you are interested in writing your thesis at our chair, please contact us or come by our offices. Below is a list of current topics we deem suitable. However, other topics probably are available at request.

Formal Capabilities of Networks

(Master thesis)

Die Systemanalyse beschränkt sich üblicherweise auf eine Betrachtung der internen Dynamik eines Systems. Systeme sind jedoch oft gar keine vollständig isolierten Objekte sondern erfüllen gewisse Funktionalitäten in Wechselwirkung mit ihrer Umgebung. Ein vollständiges Verständnis des Systemverhaltens ist dann nicht möglich, ohne auch die Interaktionen zwischen System und Umgebung zu berücksichtigen.

Eine bekannte Möglichkeit zur Beschreibung von System-Funktionalitäten ist es, diese als Process Capabilities zu repräsentieren. Anschaulich beschreibt dieser Begriff, wie häufig ein vorteilhaftes Ergebnis anteilig erzielt wird. Die klassische Formulierung von Process Capabilities ermöglicht jedoch keine Repräsentationen von Capabilities, die die innere Struktur des Systems berücksichtigen. Fragen nach der Beeinträchtigung von Capabilities aufgrund von spezifischen Beeinträchtigungen des fraglichen Systems etwa durch spezifische Faults können daher so nicht untersucht werden. Um diesen Mangel zu beseitigen, soll der Begriff der Process Capabilities auf Systeme übertragen werden, die man im Sinne einer Systemdekomposition als dynamische statistische Netzwerke auffasst. Die Dynamik solcher Netzwerke definiert auf ihnen ablaufende Prozesse, welche den Ausgangspunkt der beabsichtigten Übertragung des Capability-Begriffs von ‚black boxes‘ auf (als Netzwerk) strukturierte Systeme erlauben. Bei der Definition ist die Systemumgebung geeignet zu berücksichtigen, da die konkrete Nutzbarkeit der prinzipiell verfügbaren Capabilities natürlich von der konkreten Umgebung des Systems abhängt. Treten etwa Objekte, die durch die Capability zu bearbeiten wären, nur extrem selten auf, spielt eine prinzipiell ohnehin nur eingeschränkt vorhandene Capability keine Rolle. Man muss daher den Begriff der Capability um systemische Aspekte erweitern, d.h. um eine Beschreibung der möglichen Umwelten/Objekte für die Capabilities. Der so erhaltene Raum formaler Beschreibung möglicher Umgebungen des betrachteten Systems ist zu strukturieren und so Repräsentanten wichtiger Umgebungssituationen zu identifizieren. Entsprechend der Zielsetzung der Masterarbeit ist nun auf Basis der bisher erarbeiteten Grundlage ein Ansatz zur Beschreibung der Degradation des Netzwerks zu liefern. Dieser Ansatz soll die Effekte von Fehlern, die einzelne Netzwerkelemente betreffen, mit der durch sie direkt oder indirekt hervorgerufenen Verminderung der Capabilities in Beziehung setzen.

Optional soll in der Masterarbeit der Fall mehrerer Capabilities betrachtet werden. Dabei sind möglicherweise bestehende Korrelationen und Wechselwirkungen zwischen den verschiedenen Capabilities zu berücksichtigen. Solche Effekte entstehen beispielsweise, wenn verschiedene Capabilities auf dieselbe Objektart wirken und somit zueinander konkurrieren oder synergetisch wirken. Als mögliche Anwendung eines solchen Netzwerk-basierten Capability Begriffs sind kritische Infrastrukturen zu diskutieren, bei denen sich eine Degradation des Netzwerks nicht nur durch Faults, sondern auch durch Wartungsarbeiten ergeben kann.

Diese Arbeit wird in Zusammenarbeit mit der IABG mbh (München) durchgeführt.

Pickup and Delivery Algorithms

(Master thesis)

The Pickup and Delivery Problem consists of a graph and pairs of nodes where goods have to be picked up and delivered. The goal is to find a tour that minimizes the total time. It is a generalization of TSP where you simply have to visit all nodes.

This problem has many practical applications such as moving patients in a hospital or transporting supplies in a factory etc.

In this thesis you should implement several approaches to solve this problem and compare them. Among them are a dynamic programming approach, modelling it with a mixed integer linear program, and heuristic approaches. Where appropriate the existing approaches should also be improved both practically and with respect to their mathematically proven worst-case running times.

Moreover, the generalization to multiple vehicles will be considered, too.

This work will be carried out in cooperation with an industry partner.

Requirements

  • Knowledge of C++ or Java
  • Interest in Efficient Algorithms

Sequoia vs. The World

(Bachelor thesis)

Our program Sequoia solves EMSO-defineable problems on graphs of sufficiently small tree-width. Because the 'programming' of the algorithm—providing an MSO-formula expressing the problem at hand—is relatively easy, we would like to assess whether Sequoia can be used in practice.

To that end, this thesis would pit Sequoia against well-established solvers, like ILPs, SAT-solvers, Answer Set Programming or Pseudo-Boolean Optimization. These methods have undergone intensive testing via open competitions and a range of solvers have emerged as the current cutting edge. As a side-effect, a lot of test instances are available online. In order to compete with each such solver, such tests instance must be translated into a MSO-model checking problem over graphs. The collection of instances and conversion into equivalent formulations for Sequoia are the essential first step of the thesis—the second being the subsequent aggregation and evaluation of the experimental results.

Requirements

  • Knowledge of C/C++
  • Familiarity with Linux and BASH (or another appropriate scripting language)

References

Implementing
Preprocessing Algorithms

(Bachelor thesis)

For a long time it has been known that there exist poly-time preprocessing algorithms that, given an instance I of an ($NP$-hard) problem, generate a smaller instance $I'$ that has a solution if and only if $I$ has a solution. If we could find a function $f(n)$ that bounds the size of $I'$ it would follow that $P = NP$, so if we want to say something about the size of $I'$, we need to analyze the problem in a different way.

In the world of fixed parameter algorithms problem instances are broken up into a parameter $k$ and the usual input size $n$. Common parameters are solution size, max-degree, tree-width, etc. Such a problem is said to have a polynomial kernel if there exists a preprocessing algorithm that given an instance $(I,k)$ generates—in polynomial time—an instance $(I',k')$ such that both the size of $I'$ and $k'$ are bounded by $poly(k)$.

Many such algorithms have been known for a long time, but few have been implemented and tested. This thesis would consist of three steps:

  1. Investigate which kernelization algorithms are most likely to work in practice.
  2. Implement these.
  3. Evaluate them experimentally on synthetic and real world instances.

Requirements

  • Knowledge of C/C++
  • Familiarity with Linux and BASH (or another appropriate scripting language)

Evaluation of randomized algorithms

Randomization is a powerful method to devise exact algorithms for hard problems like Longest Path, Longest Cycle or Triangle Packing. In particular, a technique called color coding can be used in these instances. By the very nature of this approach one can obtain intermediate, i.e. non-optimal, solutions from the algorithm and thus use it as a heuristic.

The scope of this thesis would be an experimental evaluation and comparison of such algorithms against well-established techniques like integer linear programming, using both randomly generated and 'real' instances. The primary measure would be how fast an algorithm converges towards the optimal (or reasonably good) solution.

Other interesting questions include:

  • Source of randomness: does a simple linear congruential generator suffice or can a more sophisticated PRNG improve performance?
  • Heuristic distribution: using uniform distribution for the randomization hardens the algorithms against worst-case instances, but neglects structure present in specific cases. How much performance can be gained in such cases by using other distributions?

Survey of parameter-preserving reductions

In the world of fixed parameter algorithms problem instances are broken up into a paramameter $k$ and the usual input size $n$. A problem is fixed parameter tractable if it can be solved in time $O(f(k)\mathop{poly}(n))$ where $f$ is some arbitrary function.

Analogous to polynomial time reductions in the case of $NP$-hard problems, a type of reduction called parameter preserving is used to establish relations between problems in the class $FPT$. Such reductions can not only be used to re-use algorithms but also establish an internal hierarchy of running-times: informally, an increase of the parameter during the reduction hints at the target problem being 'harder' to solve than the source problem.

The goal of this thesis is to collect, categorize and develop parameter-preserving reductions. Such a catalog would constitute a valuable tool for researchers in the field.

Requirements

  • Good grasp of reductions
  • High interest in theoretical topics