Research

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.

Dynamic data streams

Data streams are generated in a variety of applications, e.g. physical experiments or sensor networks. The challenge is to cope with the enormous amount of data generated by these devices. Typically, the data streams are too large and arrive too quickly to be sent completely over a network to a central server and processed in real time. We explore the fundamentals for the design and analysis of distributed algorithms that extract useful information from streams with limited resources such as memory, communication volume and computing time.

Computer graphics: Real-time navigation in complex 3D worlds

In order to navigate in a virtual three-dimensional world and to create a realistic impression, high demands are made on data structures and algorithms which are used to manage such worlds and render them as images. We focus on the development of algorithms that can compute an approximate rendering of the virtual world in real time, depending on the viewer’s viewing position and direction. We test our approaches in applications of driver assistance systems together with partners at the Heinz Nixdorf Institute.

Ad-hoc networks in environments without infrastructure

The topology of dynamic networks changes over time, i.e. the participants join the network, leave the network or simply change their position. Sometimes such networks decompose into separate components that are no longer connected. In this context, we investigate strategies that exchange data in the network by so-called postmen. The strategies are applied and analysed in ad hoc networks of smartphones.

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 2018

Althaus, Ernst; Brinkmann, André; Kling, Peter; Meyer auf der Heide, Friedhelm; Nagel, Lars; Riechers, Sören; Sgall, Jirí; Suess, Tim: Scheduling shared continuous resources on many-cores. Journal of Scheduling, 21(1): S. 77 – 92, 2018


Benter, Markus; Knollmann, Till; Meyer auf der Heide, Friedhelm; Setzer, Alexander; Sundermeier, Jannik: A Peer-to-Peer based Cloud Storage supporting orthogonal Range Queries of arbitrary Dimension. In: Proceedings of the 4th International Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD) (accepted), 20. – 21. Aug. 2018


Drees, Maximilian; Feldotto, Matthias; Riechers, Sören; Skopalik, Alexander: Pure Nash equilibria in restricted budget games. Journal of Combinatorial Optimization 2018


Feldkord, Björn; Feldotto, Matthias; Gupta, Anupam; Guruganesh, Guru; Kumar, Amit; Riechers, Sören; Wajc, David: Fully Dynamic Bin Packing with Little Repacking. In: Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP), S. 51:1 – 51:24, 9. – 13. Jul. 2018, Schloss Dagstuhl - Leibniz-Zentrum für Informatik


Feldkord, Björn; Malatyali, Manuel; Meyer auf der Heide, Friedhelm: A Dynamic Distributed Data Structure for Top-k and k-Select Queries. In: Adventures Between Lower Bounds and Higher Altitudes - Essays Dedicated to Juraj Hromkovic on the Occasion of His 60th Birthday, S. 311 – 329, 2018


Feldkord, Björn; Meyer auf der Heide, Friedhelm: Online Facility Location with Mobile Facilities. In: Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), S. 373 – 381, 16. – 18. Jul. 2018, ACM


Feldotto, Matthias; Haake, Claus-Jochen; Skopalik, Alexander; Stroh-Maraun, Nadja: Disaggregating User Evaluations Using the Shapley Value. In: Proceedings of the 13th Workshop on the Economics of Networks, Systems and Computation (NetEcon 2018) (accepted), S. 5:1 – 5:6, Jun. 2018

Feldotto, Matthias; Leder, Lennart; Skopalik, Alexander: Congestion Games with Mixed Objectives. Journal of Combinatorial Optimization, 36(4): S. 1145 – 1167 2018


Hamann, Heiko; Markarian, Christine; Meyer auf der Heide, Friedhelm; Wahby, Mostafa: Pick, Pack, & Survive: Charging Robots in a Modern Warehouse based on Online Connected Dominating Sets. In: Fun With Algorithms (FUN), S. 22:1 – 22:13, 13. – 15. Jun. 2018


Jung, Daniel; Kolb, Christina; Scheideler, Christian; Sundermeier, Jannik: Brief Announcement: Competitive Routing in Hybrid Communication Networks. In: Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), S. 231 – 233, 16. – 18. Jul. 2018, ACM


Jung, Daniel; Kolb, Christina; Scheideler, Christian; Sundermeier, Jannik: Competitive Routing in Hybrid Communication Networks. In: Proceedings of the 14th International Symposium on Algorithms and Experiments for Wireless Networks (ALGOSENSORS) (accepted), 23. – 24. Aug. 2018


Knollmann, Till; Scheideler, Christian: A Self-Stabilizing Hashed Patricia Trie. In: Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), Springer Lecture Notes in Computer Science LNCS, Band 11201 , 4. – 7. Nov. 2018, Springer


König, Jürgen; Mäcker, Alexander; Meyer auf der Heide, Friedhelm; Riechers, Sören: Scheduling with interjob communication on parallel processors. Journal of Combinatorial Optimization, 36(4): S. 1356 – 1379, 2018


Li, Shouwei; Markarian, Christine; Meyer auf der Heide, Friedhelm: Towards Flexible Demands in Online Leasing Problems. Algorithmica, 80(5): S. 1556 – 1574, 2018


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, 36(4): S. 1168 – 1194, 2018


Markarian, Christine: An Optimal Algorithm for Online Prize-collecting Node-weighted Steiner Forest. In: International Workshop on Combinatorial Algorithms (IWOCA), 16. – 19. Jul. 2018


Markarian, Christine; Abu-Khzam, Faisal N. ; Meyer auf der Heide, Friedhelm; Schubert, Michael: Approximation and Heuristic Algorithms for Computing Backbones in Asymmetric Adhoc Networks. In: Theory of Computing Systems (TOCS), Nr. 8, S. 1673 – 1684, 2018


Meyer auf der Heide, Friedhelm; Schaefer, Johannes: Brief Announcement: Communication in Systems of Home Based Mobile Agents. In: Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), S. 359 – 361, 16. – 18. Jul. 2018, ACM


PhD Theses

Daniel Jung

Local Strategies for Swarm Formations on a Grid

My dissertation deals with the Gathering problem for swarms of n point-shaped robots on a grid, in which all robots of the swarm are supposed to gather at a previously undefined point. Special attention is paid to the strong limitation of robot capabilities. These include in particular the lack of global control, a global compass, global visibility and (global) communication skills. Furthermore, all robots are identical. The robots are given only local abilities. This includes a constant range of vision. The robots all work completely synchronously. In this work we present and analyze three different Gathering strategies in different robot models. We formally prove correctness and total running time: Chapter 4 focuses on minimizing the available robot capabilities. The underlying strategy completes the gathering in O(n²) time. For the following Chapters 5 and 6, the aim is to optimize the total running time under using only local robot capabilities: We additionally allow a constant-sized memory and a constant number of locally visible statuses (lights, flags). For the strategies of both chapters we show an asymptotically optimal running time of O(n). Unlike in Chapters 4 and 5, we additionally restrict connectivity and vision to an initially given chain connectivity in Chapter 6, where two chain neighbors must have a distance of 1 from each other. A robot can only see and interact with a constant number of its direct chain neighbors.

 

Matthias Feldotto

Approximate Pure Nash Equilibria in Congestion, Opinion Formation and Facility Location Games

This thesis investigates approximate pure Nash equilibria in different game-theoretic models. In such an outcome, no player can improve her objective by more than a given factor through a deviation to another strategy. In the first part, we investigate two variants of Congestion Games in which the existence of pure Nash equilibria is guaranteed through a potential function argument. However, the computation of such equilibria might be hard. We construct and analyze approximation algorithms that enable the computation of states with low approximation factors in polynomial time. To show their guarantees we use sub games among players, bound the potential function values of arbitrary states and exploit a connection between Shapley and proportional cost shares. Furthermore, we apply and analyze sampling techniques for the computation of approximate Shapley values in different settings. In the second part, we concentrate on the existence of approximate pure Nash equilibria in games in which no pure Nash equilibria exist in general. In the model of Coevolving Opinion Formation Games, we bound the approximation guarantees for natural states nearly independent of the specific definition of the players' neighborhoods by applying a concept of virtual costs. For the special case of only one influential neighbor, we even show lower approximation factors for a natural strategy. Then, we investigate a two-sided Facility Location Game among facilities and clients on a line with an objective function consisting of distance and load. We show tight bounds on the approximation factor for settings with three facilities and infinitely many clients. For the general scenario with an arbitrary number of facilities, we bound the approximation factor for two promising candidates, namely facilities that are uniformly distributed and which are paired.


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”, Vice Chair of the Section Information Sciences
  • 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
  • Member of Paderborn Institute for Data Science and Scientific Computing (DASCO)
  • 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 ACM-STOC TheoryFest Invited Papers Committee (2018)
  • Member of the Program Committee of the 16th Workshop on Approximation and Online Algorithms (WAOA 2018)
  • Member of the Program Committee of the 13th Workshop on Parallel Systems and Algorithms (PASA 2018)
  • Member of the Program Committee of the Doktorandenprogramm der INFORMATIK 2017
  • Co-Organizer and Reviewer for the Bundeswettbewerb Informatik 2018

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 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 – 2020

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 Warwick, Prof. Dr. Artur Czumaj, Warwick, United Kingdom
  • University of Liverpool, Prof. Dr. Martin Gairing, Liverpool, United Kingdom
  • Loughborough University, Prof. Dr. Lars Nagel, Loughborough, United Kingdom
  • KAIST, Prof. Dr. Martin Ziegler, Daejeon, South Korea
  • Carnegie Mellon University, Prof. Dr. Anupam Gupta, Pittsburgh, USA
  • Carnegie Mellon University, Dr. David Wajc, Pittsburgh, USA
  • Carnegie Mellon University, Dr. Guru Guruganesh, Pittsburgh, USA
  • IIT Delhi, Prof. Dr. Amit Kumar, New Delhi, India
  • Karls Universität Prag, Prof. Dr. Jiri Sgall, Prag, Tschechien
  • Haigazian University, Prof. Dr. Christine Markarian, Beirut, Lebanon
  • Lebanese American University, Prof. Dr. Faisal N. Abu-Khzam, Beirut, Lebanon
  • Albert-Ludwigs-Universität Freiburg, Prof. Dr. Stefan Kaufmann, Freiburg, Germany
  • Johannes Gutenberg-Universität Mainz, Prof. Dr. Ernst Althaus, Mainz, Germany
  • Johannes Gutenberg-Universität Mainz, Prof. Dr. Andre Brinkmann, Mainz, Germany
  • Ostfalia Hochschule für angewandte Wissenschaften, Prof. Dr. Tim Süß, Suderburg, Germany
  • University of Augsburg, Prof. Dr. Tobias Harks, Augsburg, Germany
  • Universität Hamburg, Junior-Professor Dr. Peter Kling, Hamburg, Germany