We are always looking for enthusiastic young people who are interested in a research project or thesis in the Bachelor, Master, and PhD programs. There are often topics available that are not listed here, so please contact us if you are interested in a project or thesis within an area of our group's research.
Contents
Cooperative Optimization Approaches for Distributing Service Points
Date: 11.02.2019
Topic for: Master Thesis
Contact: Thomas Jatschka or Günther Raidl
For many business models an optimal distribution of service points in a customer community is needed. Examples are charging/battery swapping stations of electric vehicles, bicycle/car sharing stations, and repair stations. When planning such systems, estimating under which conditions which customer demand can be fulfilled is fundamental in order to design and evaluate possible solutions. Such customer demands are usually acquired upfront e.g. using data on public transport, the street network, or surveys of potential customers. However, customer demand information determined in such ways typically is vague, and not uncommonly a system built on such assumptions is not as effective as originally hoped for due to major deviations in reality.
Alternative to acquiring demands upfront, cooperative optimization approaches incorporate potential users directly into the data acquisition as well as the optimization process. Expected benefits are a faster and cheaper data acquisition, the direct integration of users into the whole planning process, and ultimately better and more accepted optimization results. However, integrating users into the optimization progress also comes with some disadvantages. User interactions are not only considered time consuming but should also be treated as a scarce resource as a user is only willing to have a limited number of interactions with the program. A possible way to overcome these limitations is to use surrogate functions/machine learning techniques for simulating the interaction with a user.
Solving Hard Combinatorial Problems with SAT and QBF Solvers
Over the last two decades, SAT-solvers (which are programs that solve the Boolean satisfiability problem) have become surprisingly powerful and can check the satisfiability of instances with hundreds of thousands of variables in a few minutes. Among the most powerful SAT-solvers are Glucose and Lingeling.The subject for a Bachelor or Masters thesis would be to translate a hard combinatorial problem into SAT and solve it with a SAT-solver. For such a translation (often called encoding) there are usually many different approaches, and part of the thesis would be to compare different approaches experimentally on a set of problem instances.
The considered combinatorial problem can be chosen from a large pool of problems, including graph, clustering and optimization problems. Some recent research in this direction can be found here and here.
For even harder problems, like finding a winning strategy for a board game, one needs to go beyond SAT and use a QBF solver (Qute is such a solver we developed in our group).
Date: February 2018
Topic for: Bachelor/Master Theses
Contact: Stefan Szeider
Solving the Repetition-Free Longest Common Subsequence Problem by an A* Algorithm
Date: 30.01.2018
Topic for: Master Thesis
Contact: Marko Djukanovic or Günther Raidl
In the last decade combinatorial optimization problems on strings appear frequently in many applications like pattern recognition, data compression and in particular biology and genetics. We consider the Repetition-Free Longest Common Subsequence (RFLCS) problem which is stated as follows. A subsequence of a string is obtained by removing any letters of an input string. The longest common subsequence (LCS) of a set of input strings is a string that is a subsequence of all input strings and has maximum length. The RFLCS seeks a longest common subsequence of its input strings with the additional property that each letter appears only at most once.
For example: Given two strings s1="ATGCTGHAAB" and s2="AAABTGGABBE", the solution of the RFLCS is the string s="ATGB".
The RFLCS is known to be NP-hard, more precisely it is even APX-hard for only two input strings. In this project, an A-based algorithm shall be developed and compared to existing methods in the literature. The intended A algorithm can be built upon a recently developed framework addressing other LCS problem variants.
Graph Drawing
Date: September 2017
Topic for: Bachelor/Master Theses
Contact: Martin Nöllenburg
Graph Drawing is concerned with algorithms to compute geometric representations of graphs and networks. Applications of graph drawing range from graph visualizations for human users to hardware layouts and wireless routing. Scientifically, the area offers a wide spectrum of topics for student theses, from theoretical questions (e.g., existence of certain layouts or algorithms with certain properties) to practical questions of modeling the actual requirements of a particular application and designing, implementing, and evaluating algorithms for solving it.
Requirements:
- Proficiency in (graph) algorithmics
- Interest in geometry and visualization
- Practical topics: good programming skills
Algorithmic Cartography and Geometry
Date: September 2017
Topic for: Bachelor/Master Theses
Contact: Martin Nöllenburg
Digital cartography offers a wide spectrum of visualization problems that can be solved by geometric algorithms. The types of maps range from dynamic and interactive maps, e.g., on smart phones and mobile devices, to unconventional diagrammatic or schematic maps. Examples of algorithmic problems comprise label placement for map features, algorithms for constructing cartograms, or schematic destination maps. The area contains both topics with a stronger practical focus (including evaluation) or with a more theoretical focus. Thesis topics in computational geometry without direct links to cartography are also possible.
Requirements:
- Proficiency in algorithmics and geometric algorithms
- Interest in maps and interdisciplinary work
- Practical topics: good programming skills
