Algorithms and Complexity - Heinz Nixdorf Institut (HNI)

Former Research Group “Algorithms and Complexity” of the Heinz Nixdorf Institute

Prof. Dr. Friedhelm Meyer auf der Heide

„High computing performance can only be achieved with a combination of powerful computer systems and algorithms that solve the given application problems as efficiently as possible. Therefore, the development of efficient algorithms has established itself as a classical branch of computer science.”

Prof. Dr. Friedhelm Meyer auf der Heide,
Head of Chair

High Performance = Innovative Computer Systems + Efficient Algorithms

In our research area, we concentrate on solutions where current technological possibilities, such as high performance computer networks, mobile wireless communication networks or systems supported by specialised hardware, pose new challenges for algorithm development.

Prof. Dr. Friedhelm Meyer auf der Heide is in retirement since August 1st, 2023. As a consequence, we do not offer any bachelor’s or master’s theses as well as internships. The research associates are a member of Prof. Dr. Christian Scheideler’s research group starting August 1st, 2023.

Photos of the research group

Mitglieder der Fachgruppe »Algorithmen und Komplexität«, 2022

Mitglieder der Fachgruppe »Algorithmen und Komplexität«, 2019

Mitglieder der Fachgruppe »Algorithmen und Komplexität«, 2018

Mitglieder der Fachgruppe »Algorithmen und Komplexität«, 2017

Curriculum Vitae – Friedhelm Meyer auf der Heide

Friedhelm Meyer auf der Heide is Full Professor of Algorithms and Complexity at the Heinz Nixdorf Institute and the Department of Computer Science in the Faculty of Electrical Engineering, Computer Science and Mathematics at Paderborn University since 1989. He received his doctorate in mathematics from the University of Bielefeld in 1981 and habilitated in computer science at the Johann Wolfgang Goethe University in Frankfurt in 1986. From 1984 to 1985, he was a visiting researcher at IBM Research in San Jose, California, USA. From 1986 to 1989, he worked as Professor of Theoretical Computer Science in Dortmund and moved from there to Paderborn. He has been retired since 2023.

In 1986, he was awarded the prize for the best habilitation at the Johann Wolfgang Goethe University in Frankfurt. In 1992, he was awarded the Leibniz Prize of the German Research Foundation together with his colleague Burkhard Monien. In 2007, he was admitted to the German Academy of Sciences “Leopoldina”, in 2013 to the North Rhine-Westphalian Academy of Sciences, Humanities and the Arts and in 2017 to the German Academy of Science and Engineering (acatech). In 2021, he was awarded the SIROCCO Prize for Innovation in Distributed Computing. In 2024, he became an EATCS-Fellow.

Friedhelm Meyer auf der Heide was director of the DFG Research Training Group “Parallel Processor Networks in Production Technique” (1992–2001), the Collaborative Research Centers 376 “Massive Parallelism” (1995–2006) and 901 “On the Fly Computing” (2011–2023), as well as coordinator of the EU Integrated Project “Dynamically Evolving Large Scale Information Systems (DELIS)” (2004–2008). He has worked for the DFG in various functions, including as a member of the Review Board for Computer Science (2000–2008), the Heisenberg Committee and the DFG-DAAD program “Doctoral Studies at Universities in Germany” (2003, 2008). He was also a member of the Scientific Directorate of the Leibniz Center for Computer Science “Schloss Dagstuhl” (2005–2008) and the Advisory Board of the Max Planck Institute for Computer Science, Saarbrücken (2001–2011), as well as General Chair of the ACM Symposium Series “Parallelism in Algorithms and Architectures (SPAA)” (2007–2011), Head of the Federal Jury Mathematics/Computer Science of the Federal Competition “Jugend Forscht” (2007–2016) and Chairman of the Scientific Advisory Board of the Leibniz Center for Computer Science “Schloss Dagstuhl” (2014–2021). He has been a member of numerous program committees, including the SPAA, ICALP and ESA conferences. From 2007 to 2023, he was a member of the University Council of Paderborn University.

His research interests include algorithmic and complexity-theoretic issues in parallel computing, communication and data management in networks, dynamics in networks, computer graphics algorithms, and randomization methods. He is (co-)author of over 200 publications and several patents. To date, he has supervised over 50 doctorates and 14 of his students now hold professorships.

Publications by Prof. Dr. Friedhelm Meyer auf der Heide

Server Cloud Scheduling

M. Maack, F. Meyer auf der Heide, S. Pukrop, Algorithmica (2023).

DOI

On-The-Fly Computing -- Individualized IT-services in dynamic markets

C.-J. Haake, F. Meyer auf der Heide, M. Platzner, H. Wachsmuth, H. Wehrheim, On-The-Fly Computing -- Individualized IT-Services in Dynamic Markets, Heinz Nixdorf Institut, Universität Paderborn, Paderborn, 2023.

DOI PDF

Gathering a Euclidean Closed Chain of Robots in Linear Time and Improved Algorithms for Chain-Formation

J. Castenow, J. Harbig, D. Jung, T. Knollmann, F. Meyer auf der Heide, Theoretical Computer Science 939 (2023) 261–291.

DOI arXiv

A Unifying Approach to Efficient (Near-)Gathering of Disoriented Robots with Limited Visibility

J. Castenow, J. Harbig, D. Jung, P. Kling, T. Knollmann, F. Meyer auf der Heide, in: E. Hillel, R. Palmieri, E. Riviére (Eds.), Proceedings of the 26th International Conference on Principles of Distributed Systems (OPODIS) , Schloss Dagstuhl – Leibniz Zentrum für Informatik, Brussels, 2023, p. 15:1–15:25.

DOI arXiv

Unifying Gathering Protocols for Swarms of Mobile Robots

J. Castenow, J. Harbig, F. Meyer auf der Heide, in: Lecture Notes in Computer Science, Springer International Publishing, Cham, 2023.

DOI

Show all publications

DBLP

Publications by the research group

Server Cloud Scheduling

M. Maack, F. Meyer auf der Heide, S. Pukrop, Algorithmica (2023).

DOI

Scheduling with Many Shared Resources

M.A. Deppert, K. Jansen, M. Maack, S. Pukrop, M. Rau, in: 2023 IEEE International Parallel and Distributed Processing Symposium (IPDPS), IEEE, 2023.

DOI

Gathering a Euclidean Closed Chain of Robots in Linear Time and Improved Algorithms for Chain-Formation

J. Castenow, J. Harbig, D. Jung, T. Knollmann, F. Meyer auf der Heide, Theoretical Computer Science 939 (2023) 261–291.

DOI arXiv

A Unifying Approach to Efficient (Near-)Gathering of Disoriented Robots with Limited Visibility

DOI arXiv

Online load balancing on uniform machines with limited migration

M. Maack, Operations Research Letters 51 (2023) 220–225.

DOI

Show all publications

Doctorates of the research group

2025

Jonas Harbig: Forming Large Patterns from Widespread Swarms of Oblivious Robots with Limited Visibility, 31.07.2025

2024

Simon Pukrop: On Cloud Assisted, Restricted, and Resource Constrained Scheduling, 26.06.2023
Till Knollman: Online Algorithms for Allocating Heterogeneous Resources, 30.05.2023
Jannik Castenow: Local Protocols for Contracting and Expanding Robot Formation Problems, 24.05.2023

2020

Björn Feldkord: Mobile Resource Allocation, 23.01.2020

Habilitations of the research group

2008

Martin Ziegler: Real Computability and Hypercomputation, 14.3.2008

2002

Christian Schindelhauer: Communication Network Problems, 9.2002

2000

Christian Scheideler: Probabilistische Methoden für Koordinierungsprobleme, 30.06.2000

1999

Artur Czumaj: Randomization and Approximation Techniques for some Combinatorial Problems, 22.12.1999

1992

Martin Dietzfelbinger: Universal hashing in sequential, parallel, and distributed computing, 12.1992

Research projects of Prof. Dr. Friedhelm Meyer auf der Heide

Eine Person nutzt ein VR-Headset. Im Hitergrund sieht man die Sicht der Person im VirtuChemLab.

VR@UPB

2022–2026
QVM project

Prof. Dr. Friedhelm Meyer auf der Heide

2025

2024

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2008

2007

2006

2005

2004

2003

2002

2000

1999

1998

1997

1996

1995

1994

2008

2002

2000

1999

1992

VR@UPB

Di­gi­Chem­Lab

OSIgoes3D

Al­gorithms for Swarm Ro­bot­ics: Dis­trib­uted Com­put­ing meets Dy­nam­ic­al Sys­tems

Dis­DaS: Dis­trib­uted Data Streams in Dy­nam­ic En­vir­on­ments

DFG col­lab­or­at­ive re­search centre 901: “On-The-Fly Com­put­ing”

RES­IBES: Re­si­li­ence by Spon­tan­eous Vo­lun­teers Net­works for Cop­ing with Emer­gen­cies and Dis­aster

MUL­TI­PLEX: Found­a­tion­al Re­search on MUL­TIIevel com­plex net­works and sys­tems

Smart Teams: Loc­al, Dis­trib­uted Strategies for Self-Or­gan­iz­ing Ro­bot­ic Ex­plor­a­tion Teams

FRONTS: Found­a­tions of Ad­apt­ive Net­worked So­ci­et­ies of Tiny Arte­facts

AVI­PASIA: Syn­chron­ized Ana­lys­is and 3D Visu­al­iz­a­tion of Par­al­lel Dis­crete Event Sim­u­la­tion

Al­gorithm En­gin­eer­ing for Prob­lems in Com­puter Graph­ics

AE­OL­US: Al­gorithmic Prin­ciples for Build­ing Ef­fi­cient Over­lay Com­puters

DEL­IS: Dy­nam­ic­ally Evolving Large Scale In­form­a­tion Sys­tems

BAM­SI: User Sup­por­ted Ana­lys­is of Ma­ter­i­al Flow Sim­u­la­tion in Vir­tu­al En­vir­on­ments

PReSto: Pader­born Re­al­time Stor­age Net­work

Gi­gaNet­IC

Al­gorithms for Large Dy­nam­ic Geo­met­ric Graphs

AL­COM-FT: Al­gorithms and Com­plex­ity, Fu­ture Tech­no­lo­gies

Hier­arch­ic­al Real-Time Al­gorithms: Fun­da­ment­als and Walk­trough An­im­a­tion

DFG col­lab­or­at­ive re­search centre 376: “Massive Par­al­lel­ism – Al­gorithms, Design Meth­ods, Ap­plic­a­tio

Com­plex­ity of Par­al­lel Com­puters

Auto­mat­isms - Cul­tur­al Tech­niques of Com­plex­ity Re­duc­tion

In­ter­na­tion­al Gradu­ate School of Dy­nam­ic In­tel­li­gent Sys­tems

Auto­mat­ic Con­fig­ur­a­tion in Open Sys­tems

Sci­entif­ic Com­put­ing: Ap­plied Mod­el­ing and Al­gorithm De­vel­op­ment

Par­al­lel Com­puter Net­works in Pro­duc­tion Tech­no­logy (Spokes­man)

De­vel­op­ment of a Prac­tic­al The­ory for Clus­ter­ing Al­gori­htms

Al­gorithms for Data Streams

PADrend: Plat­form for Al­gorithm De­vel­op­ment and Ren­der­ing

PUB-Web: Pader­born Uni­ver­sity BSP-based Web Com­put­ing

PUB: Pader­born Uni­ver­sity BSP Lib­rary

SAHNE: A Sim­u­la­tion En­vir­on­ment for Ad Hoc Net­works

Prof. Dr. Friedhelm Meyer auf der Heide

DigiChemLab

Algorithms for Swarm Robotics: Distributed Computing meets Dynamical Systems

DisDaS: Distributed Data Streams in Dynamic Environments

DFG collaborative research centre 901: “On-The-Fly Computing”

RESIBES: Resilience by Spontaneous Volunteers Networks for Coping with Emergencies and Disaster

MULTIPLEX: Foundational Research on MULTIIevel complex networks and systems

Smart Teams: Local, Distributed Strategies for Self-Organizing Robotic Exploration Teams

FRONTS: Foundations of Adaptive Networked Societies of Tiny Artefacts

AVIPASIA: Synchronized Analysis and 3D Visualization of Parallel Discrete Event Simulation

Algorithm Engineering for Problems in Computer Graphics

AEOLUS: Algorithmic Principles for Building Efficient Overlay Computers

DELIS: Dynamically Evolving Large Scale Information Systems

BAMSI: User Supported Analysis of Material Flow Simulation in Virtual Environments

PReSto: Paderborn Realtime Storage Network

GigaNetIC

Algorithms for Large Dynamic Geometric Graphs

ALCOM-FT: Algorithms and Complexity, Future Technologies

Hierarchical Real-Time Algorithms: Fundamentals and Walktrough Animation

DFG collaborative research centre 376: “Massive Parallelism – Algorithms, Design Methods, Applicatio

Complexity of Parallel Computers

Automatisms - Cultural Techniques of Complexity Reduction

International Graduate School of Dynamic Intelligent Systems

Automatic Configuration in Open Systems

Scientific Computing: Applied Modeling and Algorithm Development

Parallel Computer Networks in Production Technology (Spokesman)

Development of a Practical Theory for Clustering Algorihtms

Algorithms for Data Streams

PADrend: Platform for Algorithm Development and Rendering

PUB-Web: Paderborn University BSP-based Web Computing

PUB: Paderborn University BSP Library

SAHNE: A Simulation Environment for Ad Hoc Networks