Forschung

Zukünftige IT-Systeme werden noch in weit stärkerem Maße als heute aus vielen unterschiedlichen Komponenten bestehen. Solche Systeme sind häufig zu groß und zu dynamisch, um zentral verwaltet werden zu können. Daher stehen bei uns algorithmische Probleme im Vordergrund, die sich mit dezentralen Methoden zur Kontrolle und Optimierung derartiger Systeme befassen.

Moderne verteilte IT-Systeme wie z. B. das Internet, Peer-to-Peer-Systeme oder drahtlose Kommunikationssysteme, aber
auch Schwärme von Sensoren oder mobilen Robotern stellen
neuartige Herausforderungen an die Algorithmenentwicklung:
Da wegen der Größe und Dynamik solcher Systeme die einzelnen
Komponenten (Peers, Roboter ...) nur sehr eingeschränkte
lokale Information über den aktuellen Zustand des Gesamtsystems
haben, müssen neu-lokale-algorithmische Methoden
zur Nutzung und Kontrolle solcher Systeme entwickelt werden.
Unserer Forschung befasst sich auf vielfältige Weise mit derartigen
lokalen Algorithmen.

Lokale Strategien in dynamischen Netzwerken

Dynamische Netzwerke, d. h. Netzwerke, deren Topologie
sich über die Zeit verändert, spielen in vielen Bereichen eine
wichtige Rolle. Sie tauchen z. B. als sogenannte Overlay-
Netzwerke zur Unterstützung von Peer-to-Peer-Systemen auf,
deren Topologie ständig durch neue Peers oder Ausscheiden
vorhandener Peers verändern. Wegen der Größe und Dynamik
derartiger Netzwerke ist es häufig nicht möglich, sie durch
eine zentrale Kontrolle zu steuern oder zu optimieren. Wir
befassen uns in diesem Umfeld insbesondere mit lokalen
Strategien, die das Netzwerk ständig an sich ändernde
Anwenderanforderungen anpassen.

Algorithmische Spieltheorie

Bei vielen aktuellen Problemen – beispielsweise bei großen
dezentralen Netzwerken – steht nicht mehr die Frage der
Lösung durch eine zentrale Autorität im Mittelpunkt, sondern
die verteilte Lösung durch eine Vielzahl von Akteuren. Hierbei
wählen Akteure ihre Strategien nach ihren eigennützigen Interessen,
was zu Lösungen führen kann, die schlechter sind als
die einer zentralen Autorität. Wir untersuchen hierbei einerseits,
wie stark der Einfluss des strategischen Handelns der
Akteure auf die Qualität der Lösungen ist. Andererseits interessiert
uns die Berechnung von Vorhersagen, zu welchen Ergebnissen
das strategische Verhalten führen kann.

Schwarmintelligenz und Evolutionäre Robotik

Technische Systeme werden immer komplexer. Wir entwickeln
biologisch inspirierte Ansätze, die aus Prinzip auf einfachen
Algorithmen aufgebaut sind aber dennoch komplexe Aufgaben
lösen können, indem viele dieser einfachen Einheiten miteinander
kooperieren. Unsere Ansätze werden durch mathematische
Modellierung unterstützt und wir testen sie in Anwendungen
verteilter Robotersysteme. Im Bereich der Evolutionären Robotik
entwickeln wir Methoden zur automatischen Erzeugung von
Robotersteuerungen. In einem Projekt das dieses Jahr gestartet
wurde, wenden wir unsere Methoden auf verteilte Robotersysteme
an, die mit Pflanzen interagieren.

Computergrafik: Echtzeitnavigation in komplexen virtuellen Szenen

Um in einem virtuellen dreidimensionalen Raum navigieren und
einen realistischen Eindruck erzeugen zu können, werden u. a.
hohe Ansprüche an Datenstrukturen gestellt, mit denen solche
Szenen verwaltet und mit denen Bilder gerendert werden. Ein
Schwerpunkt liegt bei uns auf der Entwicklung von Methoden,
die abhängig von der Blickposition und -richtung des Betrachters
in Echtzeit Entscheidungen über das für die Blickposition
effizienteste der anwendbaren Rendering-Verfahren treffen. Wir
erproben unsere Ansätze in Anwendungen zur Produktionsplanung
und -steuerung gemeinsam mit Partnern im Heinz Nixdorf Institut.



Unsere Aktivitäten 2015

Publikationen

Berssenbrügge, Jan; Wiederkehr, Olga; Jähn, Claudius; Fischer, Matthias: Anbindung des Virtuellen Prototypen an die Partialmodelle intelligenter technischer Systeme. In: 12. Paderborner Workshop Augmented & Virtual Reality in der Produktentstehung, Band 342, S. 65 – 78, 23. – 24. April 2015 Heinz Nixdorf Institut, Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn

Caragiannis, Ioannis; Fanelli, Angelo; Gravin, Nick; Skopalik, Alexander: Approximate Pure Nash Equilibria in Weighted Congestion Games: Existence, Effi cient Computation, and Structure. ACM Trans. Economics and Comput., 3(1): S. 2 2015

Cord-Landwehr, Andreas; Lenzner, Pascal: Network Creation Games: Think Global – Act Local. In: Proceedings of 40th Conference on Mathematical Foundations of Computer Science (MFCS), LNCS, Nr. 9235 , S. 248 – 260, August 2015, Springer-Verlag Berlin Heidelberg

Correll, Nikolaus; Hamann, Heiko: Probabilistic Modeling of Swarming Systems. In: Kacprzyk, Janusz; Pedrycz, Witold (Hrsg.) Springer Handbook of Computational Intelligence, S. 1423 – 1431. Springer, 2015

Degener, Bastian; Kempkes, Barbara; Kling, Peter; Meyer auf der Heide, Friedhelm: Linear & Competitive Strategies for Continuous Robot Formation Problems. ACM Transactions on Parallel Computing, 2(1): S. 2, Mai 2015

Ding, Hongli; Hamann, Heiko: Dependability in Swarm Robotics: Error Detection and Correction. In: First International Symposium on Swarm Behavior and Bio-Inspired Robotics (SWARM 2015), 2015

Divband Soorati, Mohammad; Hamann, Heiko: The Effect of Fitness Function Design on Performance in Evolutionary Robotics: The Influence of a Priori Knowledge. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2015), S. 153 – 160, New York, NY, USA, Juli 2015 ACM, ACM

Drees, Maximilian; Feldotto, Matthias; Riechers,Sören; Skopalik, Alexander: On Existence and Properties of Approximate Pure Nash Equilibria in Bandwidth Allocation Games. In: Proceedings of the 8th International Symposium on Algorithmic Game Theory (SAGT), Lecture Notes in Computer Science, Nr. 9347, S. 178 – 189, 28. – 30. Sep. 2015, Springer Berlin Heidelberg

Hamann, Heiko: Lessons from Speciation Dynamics: How to Generate Selective Pressure Towards Diversity. Artificial Life, 21(3) 2015

Hamann, Heiko; Wahby, Mostafa; Schmickl, Thomas; Zahadat, Payam; Hofstadler, Daniel; Stoy, Kasper; Risi, Sebastian; Faina, Andres; Veenstra, Frank; Kernbach, Serge; Kuksin, Igor; Kernbach, Olga; Ayres, Phil; Wojtaszek, Przemyslaw: flora robotica – Mixed Societies of Symbiotic Robot-Plant Bio-Hybrids. In: Proceedings of the 2015 IEEE Symposium on Artificial Life (IEEE ALIFE'15), 2015

Jähn, Claudius; Fischer, Matthias; Gerges, Maria; Berssenbrügge, Jan: Automatische Ableitung geometrischer Eigenschaften von Bauteilen aus dem 3-D-Polygonmodell. In: 12. Paderborner Workshop Augmented & Virtual Reality in der Produktentstehung, Band 342, S. 107 – 120, 23. – 24. April 2015 Heinz Nixdorf Institut, Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn

Kengyel, Daniela; Hamann, Heiko; Zahadat, Payam; Radspieler, Gerald; Wotawa, Franz; Schmickl, Thomas: Potential of Heterogeneity in Collective Behaviors: A Case Study on Heterogeneous Swarms. In: Principles and Practice of Multi-Agent Systems (PRIMA 2015), S. 201 – 217, 2015

Li, Shouwei; Mäcker, Alexander; Markarian, Christine; Meyer auf der Heide, Friedhelm; Riechers, Sören: Towards Flexible Demands in Online Leasing Problems. In: Proceedings of the 20th International Computing and Combinatorics Conference (COCOON), LNCS, Band 9198, S. 277 – 288, Januar 2015, Springer

Mäcker, Alexander; Malatyali, Manuel; Meyer auf der Heide, Friedhelm; Riechers, Sören: Nonpreemptive Scheduling on Machines with Setup Times. In: Proceedings of the 14th International Symposium on Algorithms and Data Structures (WADS), LNCS, Nr. 9214 , S. 542 – 553, 5. – 7. August 2015, Springer

Mäcker, Alexander; Malatyali, Manuel; Meyer auf der Heide, Friedhelm: Online Top-k-Position Monitoring of Distributed Data Streams. In: Proceedings of the 29th International Parallel and Distributed Processing Symposium (IPDPS), S. 357 – 364, 25. – 29. Mai 2015, IEEE

Markarian, Christine; Meyer auf der Heide, Friedhelm: Online Resource Leasing. In: 34th ACM Symposium on Principles of Distributed Computing (PODC), S. 343 – 344, 2015 Valentini, Gabriele; Hamann, Heiko: Time-Variant Feedback Processes in Collective Decision-Making Systems: Influence and Effect of Dynamic Neighborhood Sizes. Swarm Intelligence, 9(2-3): S. 153 – 176 2015

Valentini, Gabriele; Hamann, Heiko; Dorigo, Marco: Efficient Decision-Making in a Self-Organizing Robot Swarm: On the Speed Versus Accuracy Trade-Off. In: Proceedings of the 14th Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS 2015), S. 1305 – 1314, 2015

Valentini, Gabriele; Hamann, Heiko; Dorigo, Marco: Self-organized collective decisions in a robot swarm. In: AAAI-15 Video Proceedings, 2015, AAAI Press

Wahby, Mostafa; Divband Soorati, Mohammad; Von Mammen, Sebastian; Hamann, Heiko: Evolution of Controllers for Robot – Plant Bio-Hybdrids: A Simple Case Study Using a Model of Plant Growth and Motion. In: Proceedings. 25. Computational Intelligence Workshop, 2015

Wahby, Mostafa; Hamann, Heiko: On the Tradeoff between Hardware Protection and Optimization Success: A Case Study in Onboard Evolutionary Robotics for Autonomous Parallel Parking. In: Applications of Evolutionary Computation (EvoApplications 2015), Band 9028, S. 759 – 770, 2015, Springer

Wahby, Mostafa; Weinhold, Alexander; Hamann, Heiko: Revisiting BEECLUST: Aggregation of Swarm Robots with Adaptiveness to Different Light Settings. In: Proc. of the 9th EAI International Conference on Bio-inspired Information and Communications Technologies (BICT 2015), 2015, ACM

Zahadat, Payam; Hamann, Heiko; Schmickl, Thomas: Evolving Collective Behaviors With Diverse But Predictable Sensor States. In: 13th European Conference on Artifi cial Life (ECAL 2015), S. 174, 2015, MIT Press


Promotionen

Sebastian Abshoff
On the Complexity of Fundamental Problems in Dynamic Ad-hoc Networks
This thesis studies the complexity of fundamental problems in dynamic, i.e., time-variant, adhoc networks. Based on the model by Kuhn et al. (Symposium on Theory of Computing 2010), the network is controlled by an adaptive adversary that tries to prevent the effi cient execution of algorithms and only guarantees connectivity in each round. In this thesis, three main aspects are considered, which can be found in three different parts of the thesis. In the fi rst part, the adversary is restricted geometrically and an information dissemination problem is analyzed. The second part focusses on the counting problem (How many nodes are there in the network?) and establishes a relation to information dissemination problems. Finally, the third part studies the continuous, i. e., the repeated, computation of aggregation functions (e. g., the maximum of all inputs given to all nodes) in more stable variants of dynamic networks.

Claudius Jähn
Evaluation of Rendering Algorithms for Complex 3D Scenes
The efficiency of rendering algorithms for complex virtual 3D scenes does not only dependent on the scene's overall properties, but also on the observer's position inside the scene. To experimentally evaluate an algorithm, measurements are typically performed along a characteristic camera path. This allows only for a weak assessment of the algorithm's general performance even for a fi xed scene. I present an approach to represent aspects of an algorithm's behavior, like its running time or the number of performed operations, as position dependent scene properties. The properties' distribution can be approximated for all positions in the scene using an adaptive sampling technique. A distribution's statistical evaluation allows for a direct and objective comparison of different algorithms and parameter values. Its visualization yields intuitive insight into the algorithms behavior. Additionally, I present the point-based Progressive Blue Surfels rendering algorithm for visualizing highly complex virtual scenes. The algorithm places a sorted sequence of points on the visible surface of the scene's geometry, so that every prefi x of the points represents a complete
approximation of the geometry. By choosing the rendered sequence's length, image quality and running time can be adjusted at runtime. The presented techniques are implemented in PADrend, a rendering system specially designed for supporting the process of developing rendering algorithms.

Christine Markarian
Online Resource Leasing
Many markets have seen a shift from the idea of buying and moved to leasing instead. Arguably, the latter has been a major catalyst for their success. In the wake of this shift, we study in this thesis leasing concepts from an algorithmic perspective. In particular, we design theoretic models, study their inherent difficulty, and devise provably good (often optimal), efficient algorithms, with the goal to cope with real-world resource leasing scenarios. A major difficulty faced by most of these markets is the uncertainty of future demands. Consider a subcontractor who leases expensive resources from other companies to rent them out to clients. The subcontractor may buy long/expensive leases for some resource, just to realize later on that no more requests are issued for this resource in subsequent time steps. Or, the subcontractor may buy short leases, just to notice later on that having bought a longer lease would have cost less. In attempt to capture this difficulty, our algorithms tend to be online, thus providing solutions in the present without knowing the future.


Weitere Funktionen

Prof. Meyer auf der Heide

  • Member of the „Hochschulrat“ of the University of Paderborn
  • 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
  • DFG Special Advisor (Vertrauensdozent) of the University of Paderborn
  • Director of the NRW-Graduate School of Dynamic Intelligent Systems (one of three directors)
  • Assistant Chairman of the Paderborn Institute for Scientific Computation (PaSCo)
  • Managing Editor of „Journal of Interconnection Networks (JOIN)“, World Scientifi c Publishing
  • Editor of „Computer Science Review“, Elsevier
  • Chairman of the Scientific Advisory Board of the Leibniz-Zentrum für Informatik, Schloss Dagstuhl
  • Member of the Evaluation Committee of the Bundeswettbewerb „Jugend Forscht“, Coordinator of the section on Computer Science and Mathematics
  • Member of the Milner Award Committee, The Royal Society
  • Member of the program committee of the 34th Annual ACM Symposium on Principles of Distributed Computing (PODC 2015)
  • Member of the program committee of the workshop Parallele Algorithmen, Rechnerstrukturen und Systemsoftware (PARS 2015)
  • Member of the program committee of the 1st European Workshop on Parallel and Distributed Computing Education for Undergraduate Students (Euro-EDUPAR 2015)
  • Member of the program committee of the 40th International Symposium on Mathematical Foundations of Computer Science (MFCS 2015)

Jun.-Prof. Hamann

  • Associate editor of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) 2015
  • Organizer of the International Workshop “Methods for Self-Organizing Distributed Systems” (MeSoDiSy) 2015
  • Editorial board member of “Swarm Intelligence” (Springer), “Natural Computing” (Springer), “Frontiers in Robotics and AI” (Frontiers Media)
  • Member of the program committees of European Conference on Artifi cial Life (ECAL) 2015, Evolutionary Computation in Robotics (EvoROBOT-EvoStar) 2015, Genetic and Evolutionary Computation Conference (GECCO) 2015, Towards Autonomous Robotics Systems (TAROS) 2015, International Conference on Bio-inspired Information and Communications Technologies (BICT) 2015

Jun.-Prof. Skopalik

  • Member of the program committee of the 8th International Symposium, on Algorithmic Game Theory (SAGT 2015)
  • Member of the program committee of the 11th International Conference on Web and Internet Economics (WINE 2015)

Graduiertenprogramme

  • International Graduate School: NRW Graduate School of Dynamic Intelligent Systems
  • DFG Research Training Centre „Research Training Group Automatisms – Emerging structures in information technology, media, and culture“

Aktuelle Forschungsprojekte

DFG Collaborative Research Center 901
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.

Laufzeit: 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. In the first funding period, we focused our research on developing and analyzing algorithms, which e. g. allow the effi cient search for services, the distributed organization of actors in groups, or to adapt the positioning of resources in an overlay to better serve the requirements of the clients. This subproject is coordinated by Friedhelm Meyer auf der Heide and Christian Scheideler.

Laufzeit: 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.

Laufzeit: 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 specifications based
on examples, which were prepared by a domain expert. This subproject is coordinated by Gregor Engels, Michaela Geierhos, and Heiko Hamann.

Laufzeit: 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. First, we build on the scheduling results that were achieved in the first phase of subproject C2. Secondly, we incorporate the results of the complete subproject A2, especially the work on software-defined networking (SDN). This subproject emphasizes the collaboration between theoretical and practical computer science on closely related issues. We will examine these issues by using different methods (theoretical analysis, simulation, emulation and prototyping) on different levels of abstraction. 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.

Laufzeit: 2015 – 2019


EU project (IP) Foundational Research on MULTIlevel comPLEX networks and systems (MULTIPLEX)
MULTIPLEX is a large-scale integrating project (IP) with 17 participating research institutes from all over Europe, funded by the European Commission. It addresses the objective “Dynamics of Multi-Level Complex Systems” of the FP7-ICT work program. The project started in November 2012 and will last for 48 month. The goal of the project is to understand how multilevel complex systems evolve, and how they can be controlled and optimized. Indeed, multilevel dependencies may amplify cascading failures that might result in a sudden collapse of the entire system. Recent large-scale blackouts resulting from cascades in the power-grid coupled to the control communication system witness this point very clearly. A better understanding of multi-level systems is essential for future ICTs and for improving life quality and security in an increasingly interconnected and interdependent world. In this respect, complex networks science is particularly suitable for the many challenges that we face today, from critical infrastructures and communication systems to techno-social and socio-economic networks. In Paderborn, Friedhelm Meyer auf der Heide, Christian Scheideler and Alexander Skopalik contribute to this project.

Laufzeit: 2012 – 2016


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 algorithm 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 find 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.

Laufzeit: 2014 – 2017


“it's OWL” Cross-sectional project Human-Machine Interaction (BMBF)
The objective of the subproject is to develop a systematics for the application of VR based design review in the development processes of small and medium-sized enterprises. Here we develop an interactive walkthrough system (PADrend: Platform for Algorithm Development and Rendering) for the rendering of complex CAD data. New interface design and interaction technology provide an effi cient usability and configuration of the system. This project is funded by the Federal Ministry of Education and Research.

Laufzeit: 2012 – 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.

Laufzeit: 2015 – 2019


Wissenschaftliche Kooperationen

  • University of Liverpool, Martin Gairing, Ph.D., United Kingdom
  • University of Maastricht, Tobias Harks, Ph.D., The Netherlands
  • 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

Unsere Aktivitäten 2014

Publikationen

Abshoff, Sebastian; Cord-Landwehr, Andreas; Jung, Daniel; Skopalik, Alexander: Multilevel Network Games. In: Proceedings of the 10th International Conference on Web and Internet Economics (WINE), LNCS, Nr. 8877, S. 435 – 440, 14. – 17. Dezember 2014, Springer International Publishing Switzerland

Abshoff, Sebastian; Cord-Landwehr, Andreas; Jung, Daniel; Skopalik, Alexander: Brief Announcement: A Model for Multilevel Network Games. In: Proceedings of the 7th International Symposium on Algorithmic Game Theory, LNCS, Nr. 8768, S. 294, 30. September – 2. Oktober 2014, Springer

Abshoff, Sebastian; Markarian, Christine; Meyer auf der Heide, Friedhelm: Randomized Online Algorithms for Set Cover Leasing Problems. In: Combinatorial Optimization and Applications - 8th International Conference, COCOA 2014, Maui, Hawaii, USA, December 19-21, 2014, Proceedings, LNCS, 19. – 21. Dezember 2014, Springer

Abshoff, Sebastian; Meyer auf der Heide, Friedhelm: Continuous Aggregation in Dynamic Ad-Hoc Networks. In: Halldórsson, Magnús M. (Hrsg.) Structural Information and Communication Complexity - 21st International Colloquium, SIROCCO 2014, Takayama, Japan, July 23 – 25, 2014. Proceedings, Lecture Notes in Computer Science, Band 8576, S. 194 – 209, 23. – 25. Juli 2014, Springer

Antoniadis, Antonios; Barcelo, Neal; Consuegra, Mario; Kling, Peter; Nugent, Michael; Pruhs, Kirk; Scquizzato, Michele: Efficient Computation of Optimal Energy and Fractional Weighted Flow Trade-off Schedules. In: Proceedings of the 31st Symposium on Theoretical Aspects of Computer Science (STACS), S. 63 – 74, März 2014, Schloss Dagstuhl

Brinkmann, André; Kling, Peter; Meyer auf der Heide, Friedhelm; Nagel, Lars; Riechers, Sören; Suess, Tim: Scheduling Shared Continuous Resources on Many-Cores. In: Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), S. 128 – 137, 2014, ACM

Cord-Landwehr, Andreas; Maecker, Alexander; Meyer auf der Heide, Friedhelm: Quality of Service in Network Creation Games. In: Proceedings of the 10th International Conference on Web and Internet Economics (WINE), LNCS, Nr. 8877, S. 423 – 428, 14. – 17. Dezember 2014, Springer International Publishing Switzerland

Degener, Bastian; Kempkes, Barbara; Kling, Peter; Meyer auf der Heide, Friedhelm: Linear & Competitive Strategies for Continuous Robot Formation Problems. ACM Transactions on Parallel Computing, to appear, Dezember 2014

Drees, Maximilian; Riechers, Sören; Skopalik, Alexander: Budget-restricted utility games with ordered strategic decisions. In: Proceedings of the 7th International Symposium on Algorithmic Game Theory (SAGT), 2014

Feldotto, Matthias; Gairing, Martin; Skopalik, Alexander: Bounding the Potential Function in Congestion Games and Approximate Pure Nash Equilibria. In: Proceedings of the 10th International Conference on Web and Internet Economics (WINE), LNCS, number 8877, S. 30 – 43, 14. – 17. Dezember 2014, Springer International Publishing Switzerland

Feldotto, Matthias; Scheideler, Christian; Graffi, Kalman: HSkip+: A Self-Stabilizing Overlay Network for Nodes with Heterogeneous Bandwidths.
In: Proceedings of the 14 – th IEEE International Conference on Peer-to-Peer Computing (P2P), S. 1 – 10, 9. – 11. September 2014, IEEE

Feldotto, Matthias; Skopalik, Alexander: A Simulation Framework for Analyzing Complex Infinitely Repeated Games. In: Proceedings of the 4th International Conference on Simulation and Modeling Methodologies, Technologies and Applications (SIMULTECH 2014), S. 625 – 630, 28. – 30. August 2014, SciTePress

Flocchini, Paola; Gao, Jie; Kranakis, Evangelos; Meyer auf der Heide, Friedhelm (Hrsg.) Algorithms for Sensor Systems – 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS 2013). Lecture Notes in Computer Science, Band 8243, Sophia Antipolis, France, 2014, Springer

Gairing, Martin; Kotsialou, Grammateia; Skopalik, Alexander: Approximate pure Nash equilibria in Social Context Congestion Games. In: Proceedings of the 10th International Conference on Web and Internet Economics (WINE), LNCS, number 8877, S. 480 – 485, 14. – 17. Dezember 2014, Springer International Publishing Switzerland

Hansknecht, Christoph; Klimm, Max; Skopalik, Alexander: Approximate pure Nash equilibria in weighted congestion games. In: Proceedings of the 17th. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), LIPIcs, volume 28, S. 242 – 257, 4. – 6. September 2014, Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik

Harks, Tobias; Hoefer, Martin; Schewior, Kevin; Skopalik, Alexander: Routing Games with Progressive Filling. In: Proceedings of the 33rd Annual IEEE International Conference on Computer Communications (INFOCOM‘14), S. 352 – 360, 27. April – 2. Mai 2014, IEEE

Janiuk, Jens; Maecker, Alexander; Graffi, Kalman: Secure Distributed Data Structures for Peer-to-Peer-based Social Networks. In: Proceedings of the 2014 International Conference on Collaboration Technologies and Systems (CTS), S. 396 – 405, Mai 2014, IEEE

Kniesburges, Sebastian; Markarian, Christine; Meyer auf der Heide, Friedhelm; Scheideler, Christian: Algorithmic Aspects of Resource Management in the Cloud. In: Structural Information and Communication Complexity – 21st International Colloquium, SIROCCO 2014, Takayama, Japan, July 23 – 25, 2014. Proceedings, LNCS, S. 1 – 13, 23. – 25. Juli 2014

Lukovszki, Tamás; Meyer auf der Heide, Friedhelm: Fast Collisionless Pattern Formation by Anonymous, Position-Aware Robots. In: Principles of Distributed Systems – 18th International Conference, OPODIS 2014, Cortina d‘Ampezzo, Italy, December 16 – 19, 2014. Proceedings, Lecture Notes in Computer Science, 16. – 19. Dezember 2014, Springer


Promotionen

Peter Kling
Energy-efficient scheduling algorithms

This thesis studies the design and quality of energy-efficient scheduling algorithms, especially with respect to speed scaling.Speedscaling finds practical application in techniques like Intel‘s SpeedStep and AMD‘s PowerNOW, which allow a processor to change its speed during runtime. This way, it may use low, energy-efficient speeds during the majority of time and only enter a less energy-efficient mode when the workload becomes too high to guarantee a sufficient quality of service. Theoretical investigations of such models were initiated by Yao, Demers, and Shenker [FOCS:1995]. They combined deadline scheduling with speed scaling, striving to schedule all jobs while minimizing the total energy consumption.

The results presented in this thesis align with the rich body of literature on variants of this model. The main results are presented in four parts (Chapters 3 to 6). Parts one and two study different price-collecting variants of the original problem, where the scheduler may miss deadlines if it pays a job-specific penalty. Part three replaces the deadline constraints by the flow time objective. The last part introduces a new type of resource constrained scheduling. While it does not directly consider energy, it might be a first step towards a theoretical model where the energy source is shared between several processors.

Ralf Petring
Multi-Algorithmen-Rendering

Viele große virtuelle 3-D-Szenen sind nicht gleichmäßig strukturiert, z. B. weil sie eine stark schwankende Dichteverteilung der Geometrie aufweisen. Für solche ungleichmäßig strukturierten Szenen gibt es keinen Algorithmus, der an allen Betrachterpositionen gut funktioniert, also für beliebige Positionen ein Bild mit guter Qualität in annehmbarer Zeit darstellt. Für eine kleine Teilmenge dieser Szenen kann die Situation verbessert werden, indem ein erfahrener Benutzer per Hand für einzelne Bereiche einer Szene entscheidet, mit welchem Algorithmus diese dargestellt werden.

In dieser Arbeit wird ein Verfahren vorgestellt, welches automatisch unterschiedliche Algorithmen gleichmäßig strukturierten Bereichen einer Szene zuordnet. Die Methode teilt dafür die Szene in brauchbare Bereiche auf und misst das Verhalten unterschiedlicher Algorithmen auf diesen Bereichen in einem Vorberechnungsschritt. Zur Laufzeit werden diese Daten dann genutzt, um eine Vorhersage für die Laufzeit und den entstehenden Bildfehler der einzelnen Algorithmen auf den Bereichen der Szene abhängig von der Position des Betrachters zu erhalten. Mittels Lösens eines in einen Regelkreis eingebetteten Optimierungsproblems kann dann die Bildqualität
durch eine geschickte Zuordnung von Algorithmen zu Bereichen bei nahezu konstanter Bildrate optimiert werden. In einer experimentellen Evaluierung werden sowohl Laufzeit als auch Bildqualität unserer Methode mit denen von
Standardverfahren verglichen.


Weitere Funktionen

Prof. Meyer auf der Heide

  • Member of the „Hochschulrat“ of the University of Paderborn
  • 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
  • DFG Special Advisor (Vertrauensdozent) of the University of Paderborn
  • Director of the NRW-Graduate School of Dynamic Intelligent Systems (one of three directors)
  • Assistant Chairman of the Paderborn Institute for Scientific Computation (PaSCo)
  • Managing Editor of „Journal of Interconnection Networks (JOIN)“, World Scientific Publishing
  • Editor of „Computer Science Review“, Elsevier
  • Member of the Scientific Advisory Board of the Leibniz-Zentrum für Informatik, Schloss Dagstuhl
  • Member of the Evaluation Committee of the Bundeswettbewerb „Jugend Forscht“,
  • Coordinator of the section on Computer Science and Mathematics
  • Member of the Milner Award Committee, The Royal Society Chairman of the evaluation committee of the LOEWE-Zentrum „Center for Advanced Security Research Darmstadt (CASED)“
  • Member of the program committee of the IFIP Theoretical Computer Science Conference (TCS 2014)
  • Member of the program committee of the workshop „Parallele Algorithmen, Rechnerstrukturen und Systemsoftware (PARS)“, 2014
  • Member of the program committee of the 20st International Colloquium on Structural Information and Communication Complexity (SIROCCO 2014)
  • Member of the program committee of the 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2014)

Jun.-Prof. Skopalik

  • Organizer of the German Day on Computational Game Theory 2014

Graduiertenprogramme

  • International Graduate School: NRW Graduate School of Dynamic Intelligent Systems
  • DFG Research Training Centre „Research Training Group Automatisms – Emerging structures in information technology, media, and culture“

Aktuelle Forschungsprojekte

DFG Collaborative Research Center 901

„On-The-Fly Computing“ with the Subprojects A1 „Capabilities and limitations of local strategies in dynamic networks“ (jointly with Prof. Dr. Christian Scheideler), C2 „On-The-Fly Compute Centers“ (jointly with Jun.-Prof. Dr.- Christian Plessl, Prof. Dr. Marco Platzner), and Z (Central Duties of the CRC)

MULTIPLEX

EU-IP Foundational Research on MULTIlevel comPLEX networks and systems (MULTIPLEX)

it‘s OWL

Cross-sectional project Human-Machine-Interaction(BMBF)

DISDAS

DFG priority project: Distributed Data Streams in Dynamic Environments in the Priority Programme 1736 Algorithms for Big Data