Ehemalige Fachgruppe »Algorithmen und Komplexität« des Heinz Nixdorf Institut
Prof. Dr. Friedhelm Meyer auf der Heide
„Hohe Rechenleistung kann nur durch eine Kombination von leistungsfähigen Computersystemen und Algorithmen, die das gegebene Problem so effizient wie möglich lösen, erreicht werden. Daher hat sich die Entwicklung von effizienten Algorithmen als klassischer Zweig der Informatik etabliert.”
Hohe Rechenleistung = Innovative Computersysteme + Effiziente Algorithmen
Unsere Forschung konzentriert sich auf Fragestellungen, in denen aktuelle technische Möglichkeiten, wie z. B. Hochleistungsrechnernetzwerke, drahtlose, mobile Kommunikationsnetze oder durch Spezialhardware unterstützte Systeme, neue Herausforderungen für den Entwurf effizienter Algorithmen darstellen.
Prof. Dr. Friedhelm Meyer auf der Heide ist seit dem 1.8.2023 in Pension. Deshalb vergeben wir keine Bachelor- und Masterarbeiten und auch keine Internships mehr. Die wissenschaftlichen Mitarbeiter sind ab dem 1.8.2023 Mitglieder der Arbeitsgruppe von Prof. Dr. Christian Scheideler.
Bilder der Arbeitsgruppe
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 "Schloß 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 "Schloß Dagstuhl" (2014 - 2021). He has been a member of numerous program committees, including the SPAA, ICALP and ESA conferences.
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.
Publikationen von Prof. Dr. Friedhelm Meyer auf der Heide
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.
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.
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.
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.
Show all publications
Publikationen der Fachgruppe
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.
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.
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.
Online load balancing on uniform machines with limited migration
M. Maack, Operations Research Letters 51 (2023) 220–225.
Show all publications
Promotionen und Habilitationen der Fachgruppe
Promotionen
- Jonas Harbig: Forming Large Patterns from Widespread Swarms of Oblivious Robots with Limited Visibility, 31.07.2025
Promotionen
- 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
Promotionen
- Björn Feldkord: Mobile Resource Allocation, 23.01.2020
Promotionen
- Alexander Mäcker: On Scheduling with Setup Times, 06.11.2019
- Manuel Malatyali: Big Data: Sublinear Algorithms for Distributed Data Streams, 15.02.2019
Promotionen
- Matthias Feldotto: Approximate Pure Nash Equilibria in Congestion, Opinion Formation and Facility Location Games, 21.12.2018
- Daniel Jung: Local Strategies for Swarm Formations on a Grid, 13.02.2018
Promotionen
- Sören Riechers: Scheduling with Scarce Resources, 14.11.2017
- Pavel Podlipyan: Local Algorithms for the Continuous Gathering Problem, 08.11.2017
- Shouwei Li: Parallel fixed parameter tractable problems, 12.10.2017
Promotionen
- Max Drees: Existence and Properties of Pure Nash Equilibria in Budget Games, 27.06.2016
- Andreas Cord-Landwehr: Selfish Network Creation - On Variants of Network Creation Games, 09.02.2016
Promotionen
- Christine Markarian: Online Resource Leasing, 08.07.2015
- Claudius Jähn: Bewertung von Renderingalgorithmen
für komplexe 3-D-Szenen, 25.06.2015 - Sebastian Abshoff: On the Complexity of Fundamental Problems in
Dynamic Ad-hoc Networks, 27.04.2015
Promotionen
- Peter Kling: Energy-efficient Scheduling Algorithms, 31.03.2014
- Ralf Petring: Multi-Algorithmen-Rendering: Darstellung heterogener 3-D-Szenen in Echtzeit, 14.02.2014
Promotionen
- Benjamin Eikel: Spherical visibility sampling : preprocessed visibility for occlusion culling in complex 3D scenes, 18.12.2013
- Peter Pietrzyk: Local and Online Algorithms for Facility Location, 28.10.2013
Promotionen
- Barbara Kempkes: Local strategies for robot formation problems, 17.02.2012
Promotionen
- Tim Süß: Parallel Real-Time Rendering using Heterogeneous PC Clusters, 19.12.2011
- Sascha Effert: Verfahren zur redundanten Datenplatzierung in skalierbaren Speichersystemen, 10.05.2011
- Joachim Gehweiler: Peer-to-Peer Based Parallel Web Computing, 09.05.2011
Promotionen
- Jan Mehler: Power-Aware Online File Allocation in Dynamic Networks, 30.09.2010
- Peter Mahlmann: Peer-to-Peer Networks based on Random Graphs, 13.04.2010
- Sebastian Degener: Local, distributed approximation algorithms for geometric assignment problems, 13.04.2010
Promotionen
- Katharina Lürwer-Brüggemeier: Mächtigkeit und Komplexität von Berechnungen mit der ganzzahligen Division, 17.12.2008
- Mario Mense: On Fault-Tolerant Data Placement in Storage Networks, 16.12.2008
- Gunnar Schomaker: Distributed Resource Allocation and Management in Heterogeneous Networks, 16.12.2008
- Michael Kortenjan: Size Equivalent Cluster Trees - Rendering CAD Models in Industrial Scenes, 14.11.2008
- Olaf Bonorden: Versatility of Bulk Synchronous Parallel Computing: From the Heterogeneous Cluster to the System on Chip, 30.05.2008
Habilitationen
- Martin Ziegler: Real Computability and Hypercomputation, 14.3.2008
Promotionen
- Jaroslaw Kutylowski: Using Mobile Relays for Ensuring Connectivity in Sparse Networks, 06.12.2007
- Miroslaw Dynia: Collective Graph Exploration, 06.12.2007
Promotionen
- Gereon Frahling: Algorithms for Dynamic Geometric Data Streams, 18.10.2006
- Stefan Rührup: Position-based Routing Strategies, 31.08.2006
- Miroslaw Korzeniowski: Dynamic Load Balancing in Peer-to-Peer Networks, 05.05.2006
- Valentina Damerow: Average and Smoothed Complexity of Geometric Structures, 03.03.2006
Promotionen
- Marcin Bienkowski: Page Migration in Dynamic Networks, 16.09.2005
- Jan Klein: Efficient Collision Detection for Point and Polygon Based Models, 22.07.2005
- Klaus Volbert: Geometric Spanners for Topology Control in Wireless Networks, 14.06.2005
- Matthias Fischer: Design, Analysis, and Evaluation of a Data Structure for Distributed Virtual Environments, 18.03.2005
Promotionen
- Kay Salzwedel: Data Distribution Algorithms for Storage Networks, 16.07.2004
Promotionen
- Harald Räcke: Data management and routing in general networks, 08.12.2003
Promotionen
- Christian Sohler: Property Testing and Geometry, 18.12.2002
- Martin Ziegler: Zur Berechenbarkeit reeller geometrischer Probleme, 11.11.2002
Habilitationen
- Christian Schindelhauer: Communication Network Problems, 9.2002
Promotionen
- Ingo Rieping: Communication in Parallel Systems - Models, Algorithms and Implementations, 14.11.2000
- Matthias Westermann: Caching in Networks: Non-Uniform Algorithms and Memory Capacity Constraints, 03.11.2000
- Klaus Schröder: Balls into Bins: A Paradigm for Job Allocation, Data Distribution Processes, and Routing, 12.05.2000
Habilitationen
- Christian Scheideler: Probabilistische Methoden für Koordinierungsprobleme, 30.06.2000
Promotionen
- Tamas Lukovszki: New Results on Geometric Spanners and Their Applications, 01.10.1999
Habilitationen
- Artur Czumaj: Randomization and Approximation Techniques for some Combinatorial Problems, 22.12.1999
Promotionen
- Berthold Vöcking: Static and Dynamic Data Management Networks, 18.12.1998
- Brigitte Oesterdiekhoff: On Periodic Comparator Networks, 15.05.1998
Promotionen
- Willy-Bernhard Strothmann: Bounded Degree Spanning Trees, 19.12.1997
- Wolfgang Dittrich: Communication and I/O Efficient Parallel Data Structures, 22.08.1997
- Armin Bäumker: Communication Efficient Parallel Searching, 19.09.1997
Promotionen
- Christian Scheideler: Universal Routing Strategies for Interconnection Networks, 18.12.1996
Promotionen
- Foued Ameur: Space-Bounded Learning Algorithms, 20.12.1995
- Alf Wachsmann: Eine Bibliothek von Basisdiensten für Parallelrechner: Routing, Synchronisation, gemeinsamer Speicher, 08.09.1995
- Artur Czumaj: Parallel Algorithmic Techniques: PRAM Algorithms and PRAM Simulations, 30.08.1995
- Volker Stemann: Contention Resolution in Hashing Based Shared Memory Simulations, 06.07.1995
Promotionen
- Rolf Wanka: Paralleles Sortieren auf mehrdimensionalen Gittern, 16.09.1994
Habilitationen
- Martin Dietzfelbinger: Universal hashing in sequential, parallel, and distributed computing, 12.1992