Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
 

Current Research Projects

Our group is involved in several national and international research projects, funded by the German Research Foundation (DFG), the European Commission (EU), the Australian Research Council (ARC) and others. For a list of finished research projects, see here.

Approximating partition functions on geometric spaces (PAGES)

The proposed research aspires to start a new direction in approximate counting by investigating the effect of geometry on the computational complexity of approximating partition functions. We expect that the computational study of partition functions on geometric inputs leads to novel approximation algorithms and hardness results. These expectations are justified by the fact that the most frequent gadget used to show hardness of approximation cannot be constructed under geometric restrictions. Furthermore, recent results show a multitude of NP-hard decision problems that become tractable when their input is restricted by the effect of some geometry. This provides the opportunity to design new approximation algorithms also for the—typically even harder—counting versions of these problems. Outside the algorithmic interest of our results, we also expect new insights on the statistical physics side.

Principal Investigator: Andreas Göbel
Project term: February 2023 to January 2025
Funded by: German Research Foundation (DFG)

Computer assistance for validation and accreditation of study regulations to improve studyability (CAVAS+)

This project aims to build up and establish an AI-powered assistance system to validate study regulations. In a logic-based approach, study regulations will be made comprehensible to both machines and humans, allowing for further techniques for improving the processes involving study regulations. In addition, staff will be trained in the usage of artificial intelligence in teaching. Thus, the project is expected to benefit students as well as teaching and administrative staff. The chair for algorithm engineering contributes with research work on the foundations of artificial intelligence, as well as the usage of online judges for teaching.

Participating professors: Torsten Schaub, Ulrike Lucke (speaker), Tobias Friedrich
Project term: January 2022 to December 2025
Funded by: German Federal Ministry of Education and Research (BMBF)

Theory of Estimation-of-Distribution Algorithms

Large optimization problems are regularly not efficiently solvable by standard optimization techniques, as the objective function is only indirectly accessible. Popular heuristics are general-purpose optimizers inspired by nature, such as evolutionary computation. There are two frameworks for the status of the evolutionary search: evolutionary algorithms (EAs) and estimation-of-distribution algorithms (EDAs). While EAs have been studied theoretically for more than three decades, the theoretical analysis of EDAs only gained momentum recently. Our aim is to advance the rigorous understanding of EDAs, to reduce the gap between the theoretical results of EAs and EDAs, and to uncover the individual advantages of the respective approaches.

Principal Investigator: Tobias Friedrich
Participating Investigator: Timo Kötzing
Project term: April 2021 to April 2025
Funded by: German Research Foundation (DFG)

Algorithms, Dynamics, and Information Flow in Networks

Recent discoveries in computer science have shown that networks with certain characteristic features arise in many different aspects of our everyday lives as well as in industry, medicine and economics. This Research Unit investigates both the behavior of dynamic processes on such networks, like epidemics or opinion formation in social media, and the emergence of the networks themselves, for example the financial transaction graph of the German banking system.

Principal Investigators:  Petra Berenbrink, Nils Bertschinger, Amin Coja-Oghlan, Tobias Friedrich, Martin Hoefer (Speaker), Ulrich Meyer
Mercator Fellows:  Funda Ergun, Thomas Sauerwald
Project term: October 2020 to February 2025
Funded by: German Research Foundation (DFG)

Geometric Selfish Network Creation

Many important networks emerged from the uncoordinated interaction of selfish agents. A recent research trend is to describe the creation of such networks as a non-cooperative strategic game and the emerging networks are derived from the game's equilibrium states. Many previous models neglected that the agents are located in an underlying space and that its geometry has a strong influence on the network. This project aims at taking the next step towards a more realistic model.

Principal Investigators:  Tobias Friedrich, Pascal Lenzner
Mercator Fellows:  Davide Bilò
Project term: August 2020 to July 2025
Funded by: German Research Foundation (DFG)

Scale-Free Satisfiability

Boolean logic is the standard language to describe industrial decision problems stemming from various domains like logistics and optimization. Solving these problems corresponds to finding a satisfying assignment to the Boolean variables of a given formula. This can be found very efficiently with industrial solvers for instances with millions of variables. This practical efficiency stands in contrast to the most classical result of theoretical computer science: the proven computational hardness of propositional satisfiability (SAT). The disparity between these results is due to the stark structural differences between worst-case formulas and those that appear in practical applications. To address this, this project will study non-uniform and scale-free distributions, which appear to resemble industrial SAT instances more closely.

Principal Investigator: Tobias Friedrich
Participating Investigator: Thomas Bläsius
Mercator Fellows: Jordi Levy, Vijay Ganesh
Project term: March 2019 to February 2025
Funded by: German Research Foundation (DFG)





Completed Research Projects

The rest of this page lists our finished research projects.

The Hyperbolic Geometry of Networks

Network science is driven by the question which properties large real-world networks have and how we can exploit them algorithmically. Hyperbolic geometry has proven to be a useful tool in this regard. Our goal is to better understand the relationship between large real-world networks and hyperbolic geometry. We want to study properties of hyperbolic random graphs as well as embeddings of real-world networks into hyperbolic space. Moreover, we want to exploit these structural insights by developing algorithms that perform provably well on hyperbolic random graphs and, in turn, empirically well on real-world networks.

Principal Investigator: Tobias Friedrich
Participating Investigator: Thomas Bläsius
Project term: January 2019 to December 2023
Funded by: German Research Foundation (DFG)

Next Generation Real Estate Platform

In more and more domains, artificial intelligence facilitates and assist us in our life. Valyria, a young and visionary prop-tech start-up, aims to create a revolutionary platform, combining the real estate market and advanced computational methods. In particular, machine learning methods can improve real estate valuation and, thus, prove beneficial to both sellers and buyers. The Algorithm Engineering group, led by Prof. Dr. Tobias Friedrich, is thereby providing the machine learning expertise.

Principal Investigator: Tobias Friedrich
Project term: May 2021 to December 2022
Funded by: Investitionsbank des Landes Brandenburg (ILB)

Evolutionary Diversity Optimisation

This project aims to build up and establish the area of evolutionary diversity optimisation. The project will cover the design and application of evolutionary diversity optimisation methods to complex problems of significance and high national economic benefit and build up the theoretical foundations of these methods. The project is expected benefit decision makers by providing them a diverse set of high quality alternatives to choose from. This project will allow them to make highly informed decisions and lead to more reliable solutions for optimisation problems, in areas of high economic impact such as manufacturing and supply chain management.

Chief Investigator: Frank Neumann
Partner Investigator: Tobias Friedrich
Project term: January 2019 to December 2021
Funded by: Australian Research Council (ARC)

Virtual Compressor

The project aims at improving the reliability of turbomachinery by incorporating physical substitute models. The developed virtual compressor is part of a system for permanent machine monitoring and predictive maintenance for large turbomachinery. The solution incorporates data acquisition directly at the machine, an IoT platform for saving and visualization of the data, and machine-dependent analysis tools. Our research group is responsible for developing suitable methods from artificial intelligence for anomaly detection and forecasts.

Principal Investigator: Tobias Friedrich
Project term: November 2018 to October 2021
Funded by: Investitionsbank des Landes Brandenburg (ILB)

AI-Lab for IT Systems Engineering

The KI-LAB-ITSE is a joint initative of the six HPI research groups of Bert Arnrich, Jürgen Döllner, Tobias Friedrich, Robert Hirschfeld, Christoph Lippert and Christoph Meinel. The focus is on the topics of planning, developing and optimization of AI applications and AI systems. The chair for algorithm engineering contributes with research work on the foundations of artificial intelligence, e.g. in satisfiability and network algorithms.

Speakers: Jürgen Döllner, Tobias Friedrich (Deputy)
Project term: October 2019 to September 2021
Funded by: German Federal Ministry of Education and Research (BMBF)

Sales Comparison Approach

Rating the value of a real-estate is a complex process relying on local and global properties. Working with a couple of million real-estate valuation data provided by the Deutsche Sparkassenverlag (DSV), the International Real Estate Business School (IREBS) of the University of Regensburg and HPI's Information Systems and the Algorithm Engineering groups collaborate to automate real-estate valuation by means of data engineering and artificial intelligence.

Project Leader: Tobias Friedrich
Partners: Felix Naumann, Wolfgang Schäfers
Project term: July 2020 to September 2021
Funded by: Deutscher Sparkassenverlag (DSV)

Improving Applicability of Nature-Inspired Optimisation by Joining Theory and Practice (ImAppNIO)

This project brings together theoreticians and practitioners who are working in the field of nature-inspired search and optimization heuristics. Its goal is on one hand to make theoretical findings more accessible for researchers and engineers who are concerned with applications, on the other hand to make theoreticians aware of practical problems and the kind of questions that arise in practical applications.

Action Chairs: Thomas Jansen, Carola Doerr
Work Group Leaders: Tobias Friedrich, Christine ZargesGünther Raidl, Carlos Fonseca
Project term: March 2016 to October 2020
Funded by: European Cooperation in Science and Technology (COST)

Computing Strategic Routes

Traffic congestion is an increasingly important issue that leads to longer travel times for everyone involved. It can be tackled by strategic routing, where (re)routing recommendations are distributed by traffic authorities and taken into account by the drivers' navigation systems. This central coordination will lead to faster, greener and safer traffic. In corporation with TomTom, students work on new algorithmic approaches for efficiently computing such strategic routes.

Project Leader: Tobias Friedrich
Supervisors: Thomas Bläsius, Pascal Lenzner
Project term: October 2019 to July 2020
Partner: TomTom Berlin

The Structure of Computational Learning

This project aims at using mathematical methods to identify the theoretical foundations of the capabilities and limits of computational learning. It uses a framework for learning criteria which allows for general statements, informing about many learning criteria at once.

Principal Investigator: Timo Kötzing
Project term: September 2016 to February 2020
Funded by: German Research Foundation (DFG)

Analysis of Discrete Load Balancing on Heterogeneous Networks (ADLON)

Despite a large body of theoretical studies on load balancing, most results do not match the complex and heterogenous structure of the underlying network and the corresponding load balancing tasks. This project bridges the gap between the well-studied homogenous setting and the theoretically much less understood heterogenous load balancing problems that occur in practice.

Principal Investigator: Tobias Friedrich
Participating Investigator: Thomas Sauerwald
Project term: October 2015 to September 2019
Funded by: German Research Foundation (DFG)

Lossy Compression of Time Series Data

Time series data is data derived from consecutive measurements over time. It appears in all domains of applied science and engineering. Storing time series data can quickly overload any available storage. The random noise introduced by physical measurements fundamentally limits the achievable compression rate. We want to evaluate existing algorithms and develop new algorithms for lossy compression schemes for high-frequency time series data from different domains. The key question is what compression can be achieved without losing too much information while still being able to analyze the data and using it for modeling and statistical predictions.

Project Leader: Tobias Friedrich
Supervisors: Timo Kötzing, Manuel Rizzo, and Martin Schirneck
Project term: October 2018 to July 2019
Partner: Industrial Analytics GmbH

Theory of Swarm Algorithms and Their Effectiveness in Uncertain Environments (TOSU)

Bio-inspired swarm algorithms are well established in practice for solving optimization problems with complex constraints even in difficult domains involving uncertainty. This project analyzes theoretically swarm-based search heuristics for dynamically changing and stochastic objectives.

Principal Investigator: Tobias Friedrich
Participating Investigators: Timo KötzingFrank Neumann
Project term: June 2016 till May 2019
Funded by: German Research Foundation (DFG)

Bio-inspired Computing for Problems with Dynamically Changing Constraints

The aim of this project is to design bio-inspired computing methods for dynamically changing environments. Dynamic problems arise frequently in the areas of engineering, logistics, and manufacturing. Such problems are usually subject to a large set of constraints that change over time due to changes in resources. Algorithms that can deal with such dynamic changes would benefit decision-makers. The project aims to provide a foundational theory as the basis for the design of bio-inspired algorithms dealing with dynamically changing constraints and provide approaches for dealing with important industrial problems.

Chief Investigators: Frank NeumannZbigniew Michalewicz
Partner Investigators: Tobias FriedrichMarc Schoenauer
Project term: January 2016 till December 2018
Funded by: Australian Research Council (ARC)

Optimizing Project Schedules

All medium and large corporations are required to have their financial statements reviewed by an auditor. Each auditor has a certain set of skills and available time slots. Performing an audit requires different skills at different times. This results in a complex scenario with many hard and soft constraints to satisfy. In corporation with KPMG AG Wirtschaftsprüfungsgesellschaft, eight bachelor and three PhD students work on a new scheduling algorithm.

Project Leader: Tobias Friedrich
Supervisors: Martin Krejca, Ralf Rothenberger
Project term: October 2017 till July 2018
Partner: KPMG AG Wirtschaftsprüfungsgesellschaft

Efficient Shortest Paths on Portable Devices

The Navigation Data Standard (NDS) is a new regularization for map data used, for example, in portable navigation devices. It restricts the data to be only accessible in blocks corresponding to the earth’s grid. Due to the limited memory of portable devices, it is not possible to store the entire map in memory at once. In corporation with TomTom, five students work on new algorithmic approaches for efficient routing algorithms that load as few blocks as possible.

Project Leader: Tobias Friedrich
Supervisors: Thomas Bläsius, Gregor Lagodzinski, Martin Krejca, Ralf Rothenberger
Project term: October 2016 till July 2017
Partner: TomTom Berlin

Speed of Adaptation in Population Genetics and Evolutionary Computation (SAGE)

Biological evolution has produced an extraordinary diversity of organisms. Evolutionary computation has found many innovative solutions to optimisation and design problems. Both fields have studied the speed of adaptation independently, and with orthogonal approaches. This project brings together an interdisciplinary consortium from both fields to synergise these complementary approaches and to create the foundation of a unified quantitative theory describing the speed of adaptation in both biological and artificial evolution.

Consortium: Tobias FriedrichPer Kristian LehreTiago PaixãoDirk Sudholt
Links: Project Homepage
Project term: January 2014 till December 2016
Funded by: European Commission FP7 ICT FET Open

Parameterized Analysis of Bio-inspired Computing – From Theory to High Performing Algorithms

This project establishes the field of parameterised analysis of bio-inspired computing. It rigorously analyses features of instances of combinatorial optimisation problems and their impact on the runtime behaviour of bio-inspired computing methods such as evolutionary algorithms and ant colony optimisation.  

Chief Investigator: Frank Neumann
Partner Investigator: Tobias Friedrich
Project term: January 2014 till December 2016
Funded by: Australian Research Council (ARC)

Finding a Parking Place Quickly

Looking for a parking place in urban areas is often time consuming and stressful. Up-to-date navigation systems are barely capable of directing the driver to a good nearby parking lot. This is mostly due to missing data about available parking places on the roadside and little research on this topic. In corporation with TomTom five students work on new algorithmic approaches for efficient on-street parking.

Project Leader: Tobias Friedrich
Supervisors: Martin Krejca, Ralf Rothenberger
Project term: October 2015 till July 2016
Partner: TomTom Berlin

Average-Case Analysis of Parameterized Problems and Algorithms (ACAPA)

This project aims to analyze the average-case behavior of some known parameterized algorithms, mainly motivated by the recent encouraging experimental studies of these algorithms. Most of these studies record, compared to the worst-case analysis, a much more promising performance on real-world data.

Principal Investigator: Tobias Friedrich
Project term: December 2013 till August 2016
Funded by: German Research Foundation (DFG)

Smoothed Parameterized Complexity

Two main approaches have been considered in dealing with NP-hard problems in the last decade. One is parameterized complexity theory. The other one follows a probabilistic way of analyzing problems and algorithms. This project aims at developing the necessary tools and theories to combine parametrized and smoothed complexity.

Principal Investigator: Tobias Friedrich
Project term: January 2014 till June 2015
Funded by: German-Israeli Foundation for Scientific Research and Development

Theoretical Foundations of Swarm Intelligence

Swarm based randomized search heuristics such as ant colony optimization (ACO) and particle swarm optimization (PSO) are established in various applications and particularly in dynamic optimization problems, providing good solutions. Unlike e.g. in evolutionary algorithms (EAs), hardly any theoretical foundations existed before the project started. The main purpose of this research project was to analyze the efficiency of different approaches.

Principal Investigators: Tobias FriedrichFrank Neumann, Carsten Witt
Project term: 2009 till 2013
Funded by: German Research Foundation (DFG)