Future IT systems will be to a far greater extent than today consist of many different components. Such systems are often too large and dynamic, to be managed centrally. Therefore, we focus on algorithmic problems dealing with decentralized methods for the control and optimization of such systems.

Modern distributed IT-systems, such as the Internet, peer-topeersystems, and wireless communication systems, as wellas swarms of sensors or mobile robots, pose new challengesfor algorithm design. As their components (peers, robots, etc.)only have a limited local view of a system‘s current state, newlocal-algorithmic methods for utilizing and controlling thesesystems have to be developed. Our research addresses suchproblems from various perspectives.

Resource Management and Scheduling

In modern heterogeneous data centres, resource management gains more and more importance. Computing power, energy or data rate are only some examples for limited resources. In our workgroup, we develop approaches to make scheduling algorithms more efficient and to cope with the increasing size of computing centres. A special focus of our workgroup lies in scheduling with shared resources and the placement of resources in networks.

Local Strategies for Self-Organising Robot Swarms

In robot swarms of arbitrary size and unavailable infrastructure like, for example, on a foreign planet, the robots must calculate their action only based on local information. Hence, we develop formation strategies that do not need any global information, i. e. visibility only up to a constant distance, only local communication and no compass. Currently, we are investigating the robot gathering on an a priori undefined point. Here, the focus of our research is the optimality of the running time and the collision avoidance. We formally prove the correctness and complexity of our strategies in discrete as well as continuous synchronous time models on the grid and the Euclidean plane, respectively.

Computer Graphics: Real-Time Navigation in Complex Virtual Scenes

In order to enable navigation through a three-dimensional space and to generate a realistic impression, the data structures that maintain such scenes and render images must fulfil very ambitious requirements. We place an emphasis on the development of methods that, depending on the observer’s point of view, make real-time decisions as to which rendering method can be employed most efficiently. We test our approaches in applications for production planning and scheduling with partners at the Heinz Nixdorf Institute.

Swarm Intelligence and Evolutionary Robotics

Engineered systems are getting more and more complex. We develop bio-inspired approaches that start by principle from simple algorithms but still achieve complex tasks by cooperation of many simple entities. Our approaches are supported by mathematical modelling and we test them in applications of distributed robotics. Within the field called Evolutionary Robotics, we develop methods to automatically generate controllers for robots. In a project started this year, we apply our methods in distributed robot systems that interact with natural plants.

Algorithmic Game Theory

In many relevant problem areas, for example, in large decentralized networks, the question of resolution through a central authority is no longer the focal point. The solution is instead resolved through a multitude of actors. Here, actors chose their strategies according to their egoistic interests, which may lead to resolutions that are worse than those from a central authority are. On the one hand, we investigate how much the actor‘s strategic actions influence the resolution quality. On the other hand, we are interested in forecasting the resolutions, to which strategic actions may lead.

Publicatons 2017

Althaus, Ernst; Brinkmann, André; Kling, Peter; Meyer auf der Heide, Friedhelm; Nagel, Lars; Riechers, Sören; Sgall, Jiří; Suess, Tim: Scheduling shared continuous resources on many-cores. Journal of Scheduling: S. 1 – 16, 2017

Antoniadis, Antonios; Kling, Peter; Ott, Sebastian; Riechers, Sören: Continuous speed scaling with variability: A simple and direct approach. Theoretical Computer Science , 678: S. 1 – 13, 2017

Bemmann, Pascal; Biermeier, Felix; Bürmann, Jan; Kemper, Arne; Knollmann, Till; Knorr, Steffen; Kothe, Nils; Mäcker, Alexander; Malatyali, Manuel; Meyer auf der Heide, Friedhelm; Riechers, Sören; Schaefer, Johannes; Sundermeier, Jannik: Monitoring of Domain-Related Problems in Distributed Data Streams,. In: Proceedings of the 24th International Colloquium on Structural Information and Communication Complexity (SIROCCO) (accepted), Jun. 2017, Springer

Biermeier, Felix; Feldkord, Björn; Malatyali, Manuel; Meyer auf der Heide, Friedhelm: A Communication-Efficient Distributed Data Structure for Top-k and k-Select Queries. In: Proceedings of the 15th Workshop on Approximation and Online Algorithms (WAOA) (accepted), 7. – 8. Sep. 2017, Springer

Brandt, Sascha; Fischer, Matthias: Automatische Ableitung der Transportwege von Transportsystemen aus dem 3D-Polygonmodell. In: Wissenschaftsforum Intelligente Technische Systeme (WInTeSys) 2017, Band 369 , S. 415 – 427, 11. – 12. Mai 2017 Heinz Nixdorf Institut, Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn

Brandt, Sascha; Jähn, Claudius; Fischer, Matthias; Gerges, Maria; Berssenbrügge, Jan: Automatic Derivation of Geometric Properties of Components from 3D Polygon Models. In: Proceedings of the ASME 2017 International Design Engineering Technical Conferences & Computers and Information in Engineering Conference, Cleveland, USA, (accepted) 6. – 9. Aug. 2017, ASME

Drees, Maximilian; Feldotto, Matthias; Riechers, Sören; Skopalik, Alexander: Pure Nash Equilibria in Restricted Budget Games. In: Proceedings of the 23rd International Computing and Combinatorics Conference (COCOON), LNCS, S. 175 – 187, 3. – 5. Aug. 2017, Springer International Publishing

Feldkord, Björn; Markarian, Christine; Meyer auf der Heide, Friedhelm: Price Fluctuation in Online Leasing. In: Proceedings of the 11th International Conference on Combinatorial Optimization and Applications (COCOA) (accepted), 16. – 18. Dez. 2017, Springer

Feldkord, Björn; Meyer auf der Heide, Friedhelm: The Mobile Server Problem. In: Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), S. 313 – 319, 24. – 26. Jul. 2017, ACM

Feldotto, Matthias; Gairing, Martin; Kotsialou, Grammateia; Skopalik, Alexander: Computing Approximate Pure Nash Equilibria in Shapley Value Weighted Congestion Games. In: Proceedings of the 13th International Conference on Web and Internet Economics (WINE) (accepted), 17. – 20. Dez. 2017

Feldotto, Matthias; John, Thomas; Kundisch, Dennis; Hemsen, Paul; Klingsieck, Katrin; Skopalik, Alexander: Making Gamifi cation Easy for the Professor: Decoupling Game and Content with the StudyNow Mobile App. In: Proceedings of the 12th International Conference on Design Science Research in Information Systems and Technology (DESRIST), LNCS, S. 462 – 467, 30. Mai – 1. Jun. 2017, Springer, Heidelberg

Feldotto, Matthias; Leder, Lennart; Skopalik, Alexander: Congestion Games with Complementarities. In: Proceedings of the 10th International Conference on Algorithms and Complexity (CIAC), LNCS, S. 222 – 233, 24. – 26. Mai 2017, Springer, Heidelberg

Feldotto, Matthias; Leder, Lennart; Skopalik, Alexander: Congestion Games with Mixed Objectives. Journal of Combinatorial Optimization (accepted), Okt. 2017

John, Thomas; Feldotto, Matthias; Hemsen, Paul; Klingsieck, Katrin; Kundisch, Dennis; Langendorf, Mike: Towards a Lean Approach for Gamifying Education. In: Proceedings of the 25th European Conference on Information Systems (ECIS), S. 2970 – 2979, 5. – 10. Jun. 2017, Association for Information Systems

Jung, Daniel; Fischer, Matthias; Meyer auf der Heide, Friedhelm: Gathering Anonymous, Oblivious Robots on a Grid. In: Proceedings of the 13th International Symposium on Algorithms and Experiments for Wireless Networks (ALGOSENSORS) (accepted), Sep. 2017

Kling, Peter; Mäcker, Alexander; Riechers, Sören; Skopalik, Alexander: Sharing is Caring: Multiprocessor Scheduling with a Sharable Resource. In: Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), S. 123 – 132, Jul. 2017, ACM

Li, Shouwei; Mäcker, Alexander; Markarian, Christine; Meyer auf der Heide, Friedhelm; Riechers, Sören: Towards Flexible Demands in Online Leasing Problems. Algorithmica (accepted), 2017

Mäcker, Alexander; Malatyali, Manuel; Meyer auf der Heide, Friedhelm; Riechers, Sören: Cost-Efficient Scheduling on Machines from the Cloud. Journal of Combinatorial Optimization (accepted), 2017

Mäcker, Alexander; Malatyali, Manuel; Meyer auf der Heide, Friedhelm; Riechers, Sören: Non-Clairvoyant Scheduling to Minimize Max Flow Time on a Machine with Setup Times. In: Proceedings of the 15th Workshop on Approximation and Online Algorithms (WAOA) (accepted), 2017, Springer

Podlipyan, Pavel; Li, Shouwei; Markarian, Christine; Meyer auf der Heide, Friedhelm: A Continuous Strategy for Collisionless Gathering. In: Proceedings of the 13th International Symposium on Algorithms and Experiments for Wireless Networks (ALGOSENSORS) (accepted), Sep 2017

van Rooijen, Lorijn; Baeumer, Frederik Simon; Platenius, Marie Christin; Geierhos, Michaela; Hamann, Heiko; Engels, Gregor: From User Demand to Software Service: Using Machine Learning to Automate the Requirements Specifi cation Process. In: Fourth International Workshop on Artifi cial Intelligence for Requirements Engineering (AIRE'17) workshop – in conjuction with RE'17, 5. Sep. 2017

PhD Theses

Shouwei Li
Parallel Fixed Parameter Tractable Problems
Parameterized complexity theory provides a refined classification of intractable problems on the basis of multivariate design and complexity analysis of deterministic algorithms. We focus on the issue of which problems allow efficient fixed-parameter parallel algorithms.

We propose an efficient parallel algorithm for the general Monotone Circuit Value Problem with n gates and an underlying graph of genus k and show that the problem is in FPPT when parameterized by genus. This result implies that it is possible to find an algorithm that makes some P-complete problems fall into NC by fixing one or more non-trivial parameters. Hence, if we confine ourselves to P-complete problems, an analogy would be: FPPT is with respect to P-completeness what FPT is with respect to NP-completeness. We extend the FPPT framework to a general kernelization method called crown decomposition.

This result directly implies an efficient parallel algorithm for the parameterized vertex cover problem. Thus, the parallel crown decomposition and the parameterized vertex cover problem are in FPPT. Furthermore, we explore a parameter called modular-width and show that the Weighted Maximum Clique Problem and the Maximum Matching Problem are in FPPT when parameterized by modular-width. This result implies that, not only P-complete and NP-complete problems but also some problems that are neither known to be P-complete nor in NC, do have parameterized parallel solutions with non-trivial parameters.


Pavel Podlipyan
Local Algorithms for the Continuous Gathering Problem
We consider a group of mobile robots in the Euclidean plane. Robots have a limited vision range and do not have a central control. Each robot acts by depending solely on local information. Many algorithmic problems arise in such a setting.

In this work, we explore the continuous gathering problem. The goal is to know how fast the robots can gather in one not-predefined point in the continuous time model. In this model, each robot continuously observes its local neighborhood and adapts its speed and direction following a local rule. We present a class of algorithms, which we call the contracting algorithms, that perform gathering in time O(nd), where n is the number of robots and d is the diameter of the initial configuration. We also present several contracting algorithms and analyze their efficiency. Upper and lower bounds on the time needed to gather all robots in one not-predefined point are given. Besides that, we investigate how the use of proximity subgraphs of visibility graphs infl uences the gathering processes. Simulations exhibit a severe difference in the behavior of robots using a Gabriel or Relative Neighborhood graphs as the visibility graph. While a lot of collisions occur during the gathering process, typically only one collision (the fi nal one) takes place if robots use proximity graphs.  We present a contracting algorithm which ensures that no collision occurs during the gathering process. This algorithm requires the robots to have some additional capabilities, such as memory and chirality.


Sören Riechers
Scheduling with Scarce Resources
In today's data and computing centers, the available computing power of a system often is sufficient, but memory and the data rate become the bottleneck instead. Scheduling algorithms usually deal with the assignment of jobs to processors, but without any global constraint on the computing center as a whole.

In this thesis, new scheduling problems incorporating such global properties are introduced. Four(slightly) different models capturing aspects of these properties are studied. The first three models are similar in that a resource with a limited capacity is shared among multiple processors, and mostly the objective is to minimize the makespan, i.e., the time until all jobs are completed. The focus of the first model is on the assignment of the resource to the processors, where for each processor a queue of jobs is already fixed. The second model focuses on interjob communication, where given communication requirements between jobs need to be scheduled on a common communication channel. Finally, the third model is the most general case, where jobs with a certain resource requirement need to be scheduled on the different processors, but the resource has to be assigned as well. On the other hand, the fourth model captures possible strategies for highly dynamic systems, where constraints may even change continuously over time. Here, the energy consumption of a single processor is minimized while adhering to variable speed limits and incorporating fluctuating energy costs.

Additional Functions

Prof. Meyer auf der Heide

  • Member of the "Hochschulrat" of the Paderborn University
  • Director of the Collaborative Research Center (SFB 901) "On-The-Fly Computing"
  • Member of the German Academy of Sciences "Leopoldina"
  • Member of the NRW Academy of Sciences, Humanities and the Arts
  • Member of the National Academy of Science and Engineering "acatech"
  • DFG Special Advisor (Vertrauensdozent) of the Paderborn University
  • Assistant Chairman of the Paderborn Institute for Scientific Computation (PaSCo)
  • Advisory board member of "Journal of Interconnection Networks (JOIN)", World Scientific Publishing
  • Chairman of the Scientific Advisory Board of the Leibniz-Zentrum für Informatik, Schloss Dagstuhl
  • Member of the Milner Award Committee, The Royal Society
  • Member of the program committee of the "Doktorandensymposium der INFORMATIK 2017"
  • Member of the organisation committee of the 14th International Symposium on Pervasive Systems, Algorithms, and Networks (I-SPAN 2017)
  • Member of the program committee of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2017)
  • Member of the program committee of the 31st IEEE International Parallel & Distributed Processing Symposium (IPDPS 2017)
  • Member of the ACM-STOC TheoryFest Invited Papers Committee (2017)

Jun.-Prof. Skopalik

  • Member of the program committee of the 10th International Symposium on Algorithmic Game Theory (SAGT)

Prof. Hamann

  • Young fellow of the North Rhine-Westphalian Academy of Sciences, Humanities and the Arts
  • Associate editor of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) 2017
  • Editorial board member of “Swarm Intelligence” (Springer), “Natural Computing”(Springer), “Frontiers in Robotics and AI” (Frontiers Media)
  • Member of the program committee of the International Conference on Artifi cial Life (Alife) 2017
  • Member of the program committee of the IEEE Congress on Evolutionary Computation (CEC) 2017
  • Member of the program committee of the Evolutionary Computation in Robotics (EvoROBOT, EvoStar) 2017
  • Member of the program committee of the Genetic and Evolutionary Computation Conference (GECCO) 2017
  • Member of the program committee of the International Conference on Bio-inspired Information and Communications Technologies(BICT) 2017

School programmes

  • DFG Research Training Centre „Research Training Group Automatisms – Emerging structures in information technology, media, and culture“

Current research projects

DFG Collaborative Research Center 901 "On-The-Fly Computing"

The objective of CRC 901 – On-The-Fly Computing (OTF Computing) – is to develop techniques and processes for automatic on-the-fly configuration and provision of individual IT services out of base services that are available on world-wide markets. In addition to the configuration by special OTF service providers and the provision by what are called OTF Compute Centers, this involves developing methods for quality assurance and the protection of participating clients and providers, methods for the target-oriented further development of markets, and methods to support the interaction of the participants in dynamically changing markets. Friedhelm Meyer auf der Heide is coordinator of this collaborative research centre scince 2011.

Funding: German Research Foundation
Term: 2011 – 2019


DFG Collaborative Research Centre 901 “On-The-Fly Computing”, subproject A1 “Capabilities and limitations of local strategies in dynamic networks”

This subproject started in 2011 with the objective to explore the capabilities and limits of local methods for control and optimization of big dynamic networks. Our focus lies on overlay networks, which allow the interaction between actors of the OTF market (the clients) and service providers to support services and provide infrastructure. “Local” in this context means that the control and optimization is not performed by a central instance but distributed by the actors, based on their local information. This subproject is coordinated by Friedhelm Meyer auf der Heide and Christian Scheideler.

Funding: German Research Foundation
Term: 2015 – 2019


DFG Collaborative Research Centre 901 “On-The-Fly Computing”, subproject A3 “The market for services: Incentives, algorithms, implementation"

In subproject A3 we model and analyze the market for composed IT-services. The main challenges in the economic considerations are the composition aspect, automatization of transactions, and the dynamics of composed services. For the analysis we use and develop methods from the fi elds of non-cooperative, cooperative, and algorithmic game theory. Furthermore, the study of bounded rational behavior rests on methods from evolutionary game theory, behavioral economics and the theory of learning. This subproject is coordinated by Claus-Jochen Haake, Burkhard Hehenkamp, and Alexander Skopalik.

Funding: German Research Foundation
Term: 2015 – 2019


DFG Collaborative Research Centre 901 “On-The-Fly Computing”, subproject B1 “Parameterized Service Specifications”

In subproject B1 we deal with requirements specifications of software services. They are important for a successful search, composition, and analysis of services. In particular, we investigate means of (semi-)automatically synthesizing requirements specifi cations based on examples, which were prepared by a domain expert. This subproject is coordinated by Gregor Engels, Michaela Geierhos, and Heiko Hamann.

Funding: German Research Foundation
Term: 2015 – 2019


DFG Collaborative Research Centre 901 “On- The-Fly Computing”, subproject C4 “On-The-Fly Compute Centers II: Execution of Composed Services in Configurable Compute Centers”

In this subproject we are concerned with efficiently utilizing resources within a highly configurable compute center. We emphasizes the collaboration between theoretical and practical computer science on closely related issues. OTF Compute Centers are particularly characterized by their ability to profi tably exploit the properties of OTF services. They are therefore heterogeneous, in that they have various types of calculation units and persistent storage units. They also have one or more networks that connect these resources with each other. OTF services can be provided by a single or several interacting geographically or organizationally distributed OTF Compute Centers and, if necessary, they are supplemented by temporarily rented resources from the cloud. We will therefore develop and analyze scheduling processes, that consider the characteristics of OTF services on the one hand, and OTF Compute Centers on the other. This subproject is coordinated by Holger Karl and Friedhelm Meyer auf der Heide.

Funding: German Research Foundation
Term: 2015 – 2019


DFG project: Distributed Data Streams in Dynamic Environments (DISDAS) in the DFG-Priority Programme 1736 Algorithms for Big Data

In this project we lay the foundations for the design and analysis of distributed algorithms that continuously compute aggregated information of streams of data which are observed by a multitude of devices. These devices may be mobile, i.e. capable of moving in the plane or in space, and contain both (wireless) communication devices and sensors for observing their environment. The major challenge is to cope with the huge amount of data generated by the devices. Typically, the data streams are too big and arrive too fast to be completely stored, or sent to a central server through a network, or processed in real time. Thus we have to fi nd ways to extract useful information from the streams using restricted resources like memory, communication volume and computation time. In this project, we are developing continuous algorithms in distributed environments, taking both the dynamics of the devices and of the observed events into account. This reflects the scenario of moving people with smartphones who observe their environment. Friedhelm Meyer auf der Heide coordinates this project.

Funding: German Research Foundation
Term: 2014 – 2017

EU H2020 FET project “flora robotica: Societies of Symbiotic Robot-Plant Bio-Hybrids as Social Architectural Artifacts”

The objective is to develop tightly coupled, symbiotic relationships between robots and natural plants, in particular we investigate the potential in plant-robot societies to create architectural artifacts and living spaces. Heiko Hamann is coordinator of this European project.

Funding: European Union Horizon 2020 research and innovation programme
Term: 2015 – 2019

BMBF-Project: Resilience by Spontaneous Volunteers Networks for Coping with Emergencies and Disaster (RESIBES)

In RESIBES, we set up network of spontaneous volunteers, which can be quickly activated and deployed in a coordinated manner in a crisis. Individuals can register as so-called active or passive spontaneous volunteers in the network. Active spontaneous volunteers offer their workforce, while passive spontaneous volunteers provide material resources. In our project part, we are building a robust communication network, which in the case of application supports the coordination of the deployed spontaneous volunteers and the comprehensive assessment. Communication is also possible if the communication infrastructure is damaged or overloaded. To this end, we develop an ad-hoc network using the smartphones of the spontaneous volunteers. In Paderborn, Friedhelm Meyer auf der Heide, Matthias Fischer and Bernd Kleinjohann coordinate this project.

Funding: Federal Ministry of Education and Research
Term: 2016 – 2019

Scientific cooperations

  • University of Liverpool, Dr. Martin Gairing, United Kingdom
  • University of Augsburg, Prof. Dr. Tobias Harks
  • Universität Wien, Prof. Dr. Monika Henzinger, Austria
  • Sapienza University of Rome, Prof. Stefano Leonardi, Ph.D., Italy
  • IMT Alti Studi Lucca, Prof. Guido Caldarelli, Ph.D., Italy
  • University of Patras, CTI, Greece, and University of Liverpool, United Kingdom, Prof. Paul Spirakis
  • Universite Libre de Bruxelles, Prof. Marco Dorigo, Ph.D., Belgium
  • Otto von Guericke Universität Magdeburg, Prof. Dr. Sanaz Mostaghim, Germany
  • KAIST, Prof. Dr. Martin Ziegler, South Korea
  • University of Warwick, Prof. Dr. Artur Czumaj, United Kingdom