Ehemalige Fachgruppe Algorithmen und Komplexität des Heinz Nixdorf Institut
Prof. Dr. Friedhelm Meyer auf der Heide
Hohe Rechenleistung = Innovative Computersysteme + Effiziente Algorithmen
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.
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, 2022

2019

2018

2017

Curriculum Vitae Friedhelm Meyer auf der Heide
Friedhelm Meyer auf der Heide ist seit 1989 Professor für Algorithmen und Komplexität am Heinz Nixdorf Institut und am Institut für Informatik der Fakultät für Elektrotechnik, Informatik und Mathematik der Universität Paderborn. Er promovierte 1981 an der Universität Bielefeld in Mathematik und habilitierte sich 1986 an der Johann Wolfgang Goethe-Universität Frankfurt in Informatik. Von 1984 bis 1985 war er Gastforscher bei IBM Research in San Jose, Kalifornien, USA. 1986 bis 1989 arbeitete er als Professor (C3) für Theoretische Informatik in Dortmund und wechselte von dort nach Paderborn. Seit 2023 ist er pensioniert.
1986 wurde ihm der Preis für die beste Habilitation der Johann Wolfgang Goethe-Universität Frankfurt verliehen. 1992 wurde er gemeinsam mit seinem Kollegen Burkhard Monien mit dem Leibniz-Preis der Deutschen Forschungsgemeinschaft ausgezeichnet. 2007 wurde er in die Deutschen Akademie der Naturforscher „Leopoldina“, 2013 in die Nordrhein-Westfälische Akademie der Wissenschaften und der Künste und 2017 in die Deutsche Akademie der Technikwissenschaften (acatech) aufgenommen. 2021 wurde er mit dem SIROCCO Prize for Innovation in Distributed Computing ausgezeichnet, 2024 zum EATCS-Fellow ernannt.
Friedhelm Meyer auf der Heide war Sprecher des DFG-Graduiertenkollegs „Parallele Rechnernetze in der Produktionstechnik“ (1992-2001), der Sonderforschungsbereiche 376 „Massive Parallelität“ (1995-2006) und 901 "On the Fly Computing" (2011-2023), sowie Koordinator des EU-Integrierten Projekts „Dynamically Evolving Large Scale Information Systems (DELIS)“ (2004-2008) . Er war in verschiedenen Funktionen für die DFG tätig, u. a. als Mitglied des Fachkollegiums Informatik (2000-2008), des Heisenberg-Ausschusses und des DFG-DAAD Programms "Promotion an Hochschulen in Deutschland" (2003, 2008). Zudem war er Mitglied des wissenschaftlichen Direktoriums des Leibniz-Zentrums für Informatik „Schloß Dagstuhl“ (2005-2008) und des Fachbeirats des Max-Planck-Instituts für Informatik, Saarbrücken (2001-2011), sowie General Chair der ACM-Symposiums-Reihe „Parallelism in Algorithms and Architectures (SPAA)“ (2007-2011), Leiter der Bundes-Jury Mathematik/Informatik des Bundeswettbewerbs “Jugend Forscht“ (2007-2016) und Vorsitzender des Wisssenschaftlichen Beirats des Leibniz-Zentrums für Informatik „Schloß Dagstuhl“ (2014 - 2021). Er war Mitglied zahlreicher Programmkomitees, als Leiter u.a. für die Tagungen SPAA, ICALP und ESA.
Seine Forschungsinteressen beinhalten algorithmische und komplexitätstheoretische Fragestellungen zu parallelem Rechnen, Kommunikation und Datenverwaltung in Netzwerken, Dynamik in Netzwerken, Algorithmen der Computergraphik, sowie Randomisierungsmethoden. Er ist (Co-)Author von über 200 Publikationen und mehreren Patenten. Bisher wurden über 50 von ihm betreute Promotionen abgeschlossen, 14 seiner Schüler haben mittlerweile Professuren inne.
Publikationen
Promotionen und Habilitationen der Fachgruppe
2023
- 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
2019
- Alexander Mäcker: On Scheduling with Setup Times, 06.11.2019
- Manuel Malatyali: Big Data: Sublinear Algorithms for Distributed Data Streams, 15.02.2019
2018
- 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
2017
- 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
2016
- 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
2015
- 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
2014
- Peter Kling: Energy-efficient Scheduling Algorithms, 31.03.2014
- Ralf Petring: Multi-Algorithmen-Rendering: Darstellung heterogener 3-D-Szenen in Echtzeit, 14.02.2014
2013
- 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
2012
- Barbara Kempkes: Local strategies for robot formation problems, 17.02.2012
2011
- 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
2010
- 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
2008
- 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
2007
- Jaroslaw Kutylowski: Using Mobile Relays for Ensuring Connectivity in Sparse Networks, 06.12.2007
- Miroslaw Dynia: Collective Graph Exploration, 06.12.2007
2006
- 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
2005
- 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
2004
- Kay Salzwedel: Data Distribution Algorithms for Storage Networks, 16.07.2004
2003
- Harald Räcke: Data management and routing in general networks, 08.12.2003
2002
- Christian Sohler: Property Testing and Geometry, 18.12.2002
- Martin Ziegler: Zur Berechenbarkeit reeller geometrischer Probleme, 11.11.2002
2000
- 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
1999
- Tamas Lukovszki: New Results on Geometric Spanners and Their Applications, 01.10.1999
1998
- Berthold Vöcking: Static and Dynamic Data Management Networks, 18.12.1998
- Brigitte Oesterdiekhoff: On Periodic Comparator Networks, 15.05.1998
1997
- 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
1996
- Christian Scheideler: Universal Routing Strategies for Interconnection Networks, 18.12.1996
1995
- 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
1994
- Rolf Wanka: Paralleles Sortieren auf mehrdimensionalen Gittern, 16.09.1994
Habilitationen
- Martin Ziegler: Real Computability and Hypercomputation, 14.3.2008
- Christian Schindelhauer: Communication Network Problems, 9.2002
- Christian Scheideler: Probabilistische Methoden für Koordinierungsprobleme, 30.06.2000
- Artur Czumaj: Randomization and Approximation Techniques for some Combinatorial Problems, 22.12.1999
- Martin Dietzfelbinger: Universal hashing in sequential, parallel, and distributed computing, 12.1992
Forschungsprojekte
Projekte
- DigiChemLab (2020)
- OSIgoes3D
- DFG: Algorithms for Swarm Robotics: Distributed Computing meets Dynamical Systems (2021)
- DFG-Schwerpunktprojekt: Distributed Data Streams in Dynamic Environments im Schwerpunktprogramm 1736 Algorithms for Big Data (2014)
- DFG-Sonderforschungsbereich 901: On-The-Fly Computing (2011-2023)
- BMBF-Projekt: RESIBES: RESIlienz durch Helfernetzwerke zur BEwältigung von KriSen und Katastrophen (Resilience by Spontaneous Volunteers Networks for Coping with Emergencies and Disaster) (2016-2019)
- EU-Projekt (IP):Foundational Research on MULTIIevel complex networks and systems (MULTIPLEX) (2012-2016)
- DFG-Schwerpunktprojekt:Smart Teams: Local, Distributed Strategies for Self-Organizing Robotic Exploration Teams im Schwerpunktprogramm 1183 Organic Computing (2005-2011)
- EU-Projekt: Foundations of Adaptive Networked Societies of Tiny Artefacts (FRONTS) (2008-2011)
- DFG-Projekt: Synchronisierte Analyse und 3D-Visualisierung paralleler Ablaufsimulationen in interaktiv erstellten Ausprägungen (AVIPASIA), (mit W. Dangelmaier, M. Fischer, 2007-2010)
- DFG-Schwerpunktprojekt: Algorithm Engineering für Probleme der Computergrafik im Schwerpunktprogramm 1307 Algorithm Engineering (mit M. Fischer 2007-2010)
Im Rahmen des Projektes entstandene Softwarelibrary: - EU-Projekt: Algorithmic Principles for Building Efficient Overlay Computers (AEOLUS) (2005-2010)
- EU-Projekt: Dynamically Evolving Large Scale Information Systems (DELIS) (2004-2008)
- DFG-Projekt: Benutzerunterstützte Analyse von Materialflussimulationen in virtuellen Umgebungen (BAMSI), (mit W. Dangelmaier, 2003-2007)
- DFG-Projekt: Paderborn Realltime Storage Network (PReSto) - Entwicklung eines parallelen Speichersystems (mit U. Rückert, 2003-2005) V:Drive – Intelligente Lösungen zum Speichermanagement
- BMBF-Projekt: GigaNet-IC (mit Infineon Technologies AG, Rückert, Ramacher, Kastens, 2002)
- DFG-Schwerpunktprojekt: Algorithmik großer dynamischer geometrischer Graphen (2001-2009) im Schwerpunktprogramm 1126 Algorithmik großer und komplexer Netzwerke
- EU-Projekt: Algorithms and Complexity, Future Technologies (ALCOM-FT) (2000-2003)
- DFG-Schwerpunktprojekt: Hierarchische Realzeitalgorithmen: Grundlagen und Walktrough-Animation im Schwerpunktprogramm 731 Effiziente Algorithmen für diskrete Probleme und ihre Anwendungen (1996-2001)
- DFG-Sonderforschungsbereich 376: Massive Parallelität - Algorithmen, Entwurfsmethoden, Anwendungen (1995-2006)
Projekte im SFB 376 :- Zentrale organisatorische Dienste (Leitung des SFB)
- Eine realitätsnahe Theorie effizienter paralleler Algorithmen
- Universelle Basisdienste (mit B. Monien)
- Realzeitfähiger Datenserver: Scheduling, Routing, Chip-Design (mit B. Monien, U. Rückert, 1998-2000)
- Mobile Ad-hoc-Netzwerke (mit C. Schindelhauer, U. Rückert, 2001-2006)
Im Rahmen des SFB 376 entstandene Softwarelibraries:
- DFG-Schwerpunktprojekt: "Komplexität paralleler Rechner" im Schwerpunktprogramm "Datenstrukturen und effiziente Algorithmen" (mit I. Wegener, 1986-1991)
Graduiertenkollegs
- DFG-Graduiertenkolleg: Automatismen - Kulturtechniken zur Reduzierung von Komplexität
- NRW-Graduiertenkolleg: International Graduate School of Dynamic Intelligent Systems
- PACE - Paderborn Institute for Advanced Studies in Computer Science and Engineering
- Graduiertenkolleg: GSANS - the Paderborn Graduate School on Applied Network Science
- DFG-Graduiertenkolleg 776: Automatische Konfigurierung in offenen Systemen (2002-2005)
- DFG-Graduiertenkolleg 693: Wissenschaftliches Rechnen: Anwendungsorientierte Modellierung und Algorithmenentwicklung (2001-2010)
- DFG-Graduiertenkolleg: Wissenschaftliches Rechnen (PaSCo: Paderborn Institute for Scientific Computation, 2000-2011)
- DFG-Graduiertenkolleg 124: Parallele Rechnernetzwerke in der Produktionstechnik (Sprecher, 1995-2001)
Projekte von Christian Sohler in Paderborn
- DFG-Schwerpunktprojekt: Entwicklung einer praxisnahen Theorie für Clusteringalgorithmen durch datengetriebene Modellierung und Analyse im Schwerpunktprogramm 1307 Algorithm Engineering (mit J. Blömer, 2007-2013)
- DFG-Projekt: Algorithmen für Datenströme (2006-2010)