Research

Print

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 computer systems provide extended usages in many respects:

  • » The Internet enables worldwide communication and has the potential, to function as a giant parallel computer.
  • » Peer-to-Peer networks facilitate the support of distributed applications through the adaptation of the network topology.
  • Wireless communication systems allow for very flexible communication, also between mobile stations.
  • Swarms of sensors or mobile robots exploit new application scenarios.
  • Hardware support for graphics scenarios enables real-time navigation through very complex virtual scenes.

Systems, which consist of various components and whose structure changes over time, pose a special challenge. Thereby we see a mutual challenge: components (peers, robots, ...) only have a limited local view on a system's current condition; a globally good state has to be generated and maintained through simple, local rules.


Presently, the following topics are central to our research interests:


Local strategies in dynamic networks

Dynamic networks, that is networks, whose topology changes over time, play an important role in many areas. E.g. they surface as so-called overlay networks for the support of peer-to-peer systems, whose topology has to be constantly adapted to users' requirements. Also, movement patterns of robot swarms constitute dynamic networks. Further examples are data structures for mobile objects in computer graphics or wireless, mobile communication systems. Due to such networks' size and dynamics, it is often impossible to operate and optimize them through central control. Instead, the nodes themselves have to decide upon their actions, whereby they only possess very limited, local information on the overall network. On the other hand, such local strategies, conducted in the networks' nodes, should lead to globally good behavior. The development of such local strategies in various application scenarios is an essential research topic in our research group.


Algorithmic game theory

In many relevant problems - e.g. in large decentralized networks - the question of resolution through a central authority is no longer the focal point, but the distributed resolution through a multitude of actors. Here, actors chose their strategies according to their egoistic interests, which may lead to resolutions, worse than those from a central authority.

On the one hand, we investigate how much the actor's strategic actions influence the resolution's quality. On the other hand, we are interested in forecasting, to which resolutions strategic actions may lead.


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, which maintain such scenes and render images, have to meet very high requirements. We emphasize on the development of methods, which, in accordance to the observer's point of view, take real-time decisions on which rendering method can be employed most efficiently. We test our approaches in applications on production planning and scheduling with partners at the Heinz Nixdorf Institute.

Our Activities 2012

Publications:

Cord-Landwehr, Andreas; Kling, Peter; Mallmann-Trenn, Frederik: Slow Down & Sleep for Profit in Online Deadline Scheduling. In: Proceedings of the 1st Mediterranean Conference on Algorithms (MedAlg), Dec 2012, Springer-Verlag

Cord-Landwehr, Andreas; Hüllmann, Martina; Kling, Peter; Setzer, Alexander: Basic Network Creation Games with Communication Interests. In: Algorithmic Game Theory, SAGT 2012, Lecture Notes in Computer Science, number 7615 , pp. 72-83, 22 - 23 Oct 2012, Springer-Verlag


Fanelli, Angelo; Moscardelli, Luca ; Skopalik, Alexander: On the Impact of Fair Best Response Dynamics. In: Mathematical Foundations of Computer Science 2012, Sep 2012, Springer-Verlag

Süß, Tim; Koch, Clemens; Jähn, Claudius; Fischer, Matthias; Meyer auf der Heide, Friedhelm: Asynchronous Occlusion Culling on Heterogeneous PC Clusters for Distributed 3D Scenes. In: Proceedings of International Symposium on Visual Computing (ISVC), Lecture Notes in Computer Science, volume 7431 , pp. 502-512, 16 - 18 July 2012, Springer-Verlag

Kling, Peter; Meyer auf der Heide, Friedhelm; Pietrzyk, Peter: An Algorithm for Online Facility Leasing. In: Proceedings of the 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO), Lecture Notes in Computer Science, volume 7355 , pp. 61--72, 30 June - 2 July 2012, Springer-Verlag

Damerow, Valentina; Manthey, Bodo; Meyer auf der Heide, Friedhelm; Räcke, Harald; Scheideler, Christian; Sohler, Christian; Tantau, Till: Smoothed Analysis of Left-To-Right Maxima with Applications. ACM Transactions on Algorithms, 8(3)(30), July 2012

Kempkes, Barbara; Kling, Peter; Meyer auf der Heide, Friedhelm: Optimal and Competitive Runtime Bounds for Continuous, Local Gathering of Mobile Robots. In: Proceedings of the 24th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), ACM International Conference Proceeding Series, pp. 18--26, 25 - 27 June 2012

Kempkes, Barbara; Meyer auf der Heide, Friedhelm: Continuous Local Strategies for Robotic Formation Problems. In: Proceedings of the 11th International Symposium on Experimental Algorithms - SEA, Lecture Notes in Computer Science, volume 7276 , pp. 9-17, June 2012, Springer-Verlag

Caragiannis, Ioannis; Fanelli, Angelo; Gravin, Nick; Skopalik, Alexander: Computing approximate pure Nash equilibria in congestion games. SIGecom Exchanges, 11(1): pp. 26-29 2012

Caragiannis, Ioannis; Fanelli, Angelo; Gravin, Nick; Skopalik, Alexander: Approximate pure Nash equilibria in weighted congestion games: existence, efficient computation, and structure. In: ACM Conference on Electronic Commerce, 1 Jan 2012, ACM

Drees, Maximilian; Hüllmann, Martina; Koutsopoulos, Andreas ; Scheideler, Christian: Self-Organizing Particle Systems. In: Proceedings of the 26th IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2012

Brandes, Philipp; Meyer auf der Heide, Friedhelm: Distributed Computing in Fault-Prone Dynamic Networks. In: 4th Workshop on Theoretical Aspects of Dynamic Distributed Systems (TADDS 2012, to appear), 2012

 

PhD Theses

Barbara Kempkes:

Local strategies for robot formation problems

We consider a team of autonomous mobile robots in the Euclidean plane. There is no central control and the robots have to coordinate themselves. The key challenge is that each robot can only see its immediate neighbors and can also communicate only with robots in this neighborhood. This results in many algorithmic problems. This dissertation examines the conditions under which the robots can gather in one point respectively form a line between two fixed stations. For both problems, several robot strategies are presented in various models. These strategies are examined for their efficiency; Upper and lower bounds for the required number of rounds as well as the travelled distance are shown. In some cases, we also compare the distance traveled when using our strategies to the distance needed by an optimal global algorithm. Like this, competitive factors are derived.

Tim Süß:

Parallel real-time rendering using heterogeneous PC clusters

Often 3D scenes created with CAD applications have a high geometric complexity.There are several concepts (like out-of-core rendering, levels of detail, parallel rendering) to render such scenes in real-time.This dissertation focuses on the usage of heterogeneous PC clusters for parallel real-time rendering of highly complex scenes.For three different scene types specific rendering approaches were developed, where a small group of high-end computers is supported by a large number of weaker PC cluster nodes.The first scene type consists of static scenes that can be stored completely in a single computer's main memory, while the scenes of the second type exceed this memory limitations.The scenes of the last type contain not only static but also dynamic objects.

Additional functions

Friedhelm 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“
  • 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
  • Member of the program committee of the workshop “Parallele Algorithmen, Rechnerstrukturen und Systemsoftware (PARS)“, 2012
  • Member of the program committee of the 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2012)
  • Member of the Evaluation Committee of the Bundeswettbewerb “Jugend Forscht“, Coordinator of the section on Computer Science and Mathematics.
  • Member of the Award Committee of the European Association for Theoretical Computer Science (EATCS)
  • Member of the Milner Award Committee

School programmes

  • International Graduate School: NRW Graduate School of Dynamic Intelligent Systems
  • GSANS - the Paderborn Graduate School on Applied Network Science
  • 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“ 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)

DFG-SmartTeams:
DFG-Schwerpunktprogramm 1183 „Organic Computing“ mit dem Projekt: „Smart Teams“ (zusammen mit Prof. Dr. rer. nat. Christian Schindelhauer, Freiburg)

Our Activities 2011

Publications

Gehweiler, Joachim; Kling, Peter; Meyer auf der Heide, Friedhelm: An Experimental Comparison of Load Balancing Strategies in a Web Computing Environment. In: Wyrzykowski, Roman (Hrsg.) Proceedings of the 9th International Conference on Parallel Processing and Applied Mathematics, LNCS, 2011

Abshoff, Sebastian; Cord-Landwehr, Andreas; Degener, Bastian; Kempkes, Barbara; Pietrzyk, Peter: Local Approximation Algorithms for the Uncapacitated Metric Facility Location Problem in Power-Aware Sensor Networks. In: Proceedings of 7th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities, LNCS, 2011

Cord-Landwehr, Andreas; Degener, Bastian; Fischer, Matthias; Hüllmann, Martina; Kempkes, Barbara; Klaas, Alexander; Kling, Peter; Kurras, Sven; Märtens, Marcus; Meyer auf der Heide, Friedhelm; Raupach, Christoph; Swierkot, Kamil; Warner, Daniel; Weddemann, Christoph; Wonisch, Daniel: A new Approach for Analyzing Convergence Algorithms for Mobile Robots. In: Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP 2011), LNCS, volume 6756, pp. 650--661, 2011

Kling, Peter; Meyer auf der Heide, Friedhelm: Convergence of Local Communication Chain Strategies via Linear Transformations. In: Proceedings of the 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 159--166, 2011

Eikel, Benjamin; Jähn, Claudius; Petring, Ralf: PADrend: Platform for Algorithm Development and Rendering. In: Gausemeier, Jürgen; Grafe, Michael; Meyer auf der Heide, Friedhelm (Hrsg.) Augmented & Virtual Reality in der Produktentstehung, HNI-Verlagsschriftenreihe, Band 295, pp. 159--170, Heinz Nixdorf Institut, Universität Paderborn, 2011

Süß, Tim; Koch, Clemens; Jähn, Claudius; Fischer, Matthias: Approximative occlusion culling using the hull tree. In: Proceedings of Graphics Interface 2011, pp. 79--86, Canadian Human-Computer Communications Society, 2011

Süß, Tim; Jähn, Claudius; Fischer, Matthias; Meyer auf der Heide, Friedhelm; Koch, Clemens: Ein paralleles Out-of-Core Renderingsystem für Standard-Rechnernetze. In: Gausemeier, Jürgen; Grafe, Michael; Meyer auf der Heide, Friedhelm (Hrsg.) Augmented & Virtual Reality in der Produktentstehung, HNI-Verlagsschriftenreihe, Band 295, S. 185--197, Heinz Nixdorf Institut, Universität Paderborn, 2011

Degener, Bastian; Fekete, Sándor; Kempkes, Barbara; Meyer auf der Heide, Friedhelm: A survey on relay placement with runtime and approximation guarantees. Computer Science Review, 5(1): pp. 57-68, 2011

Cord-Landwehr, Andreas; Degener, Bastian; Fischer, Matthias; Hüllmann, Martina; Kempkes, Barbara; Klaas, Alexander; Kling, Peter; Kurras, Sven; Märtens, Marcus; Meyer auf der Heide, Friedhelm; Raupach, Christoph; Swierkot, Kamil; Warner, Daniel; Weddemann, Christoph; Wonisch, Daniel: Collisionless Gathering of Robots with an Extent. In: 37th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2011), LNCS, volume  6543, pp. 178-189, 2011

Schumacher, Tobias; Süß, Tim; Plessl, Christian; Platzner, Marco: FPGA Acceleration of Communication-Bound Streaming Applications: Architecture Modeling and a 3D Image Compositing Case Study. International Journal of Reconfigurable Computing, pp. 1--11, 2011

Renken, Hendrik; Laroque, Christoph; Fischer, Matthias: An Easy Extendable Modeling Framework for Discrete Event Simulation Models and their Visualization. In: Proceedings of The 25th European Simulation and Modelling Conference - (ESM'11), 2011

Degener, Bastian; Kempkes, Barbara; Langner, Tobias; Meyer auf der Heide, Friedhelm; Wattenhofer, Roger: A tight runtime bound for synchronous gathering of autonomous robots with limited visibility. In: Proceedings of the 23rd annual ACM symposium on parallel algorithms and architectures (SPAA'11), pp. 139-147, 2011

Klaas, Alexander; Laroque, Christoph; Fischer, Matthias; Dangelmaier, Wilhelm: Simulation Aided, Knowledge Based Routing for AGVs in a Distribution Warehouse. In: Proceedings of the 2011 Winter Simulation Conference, 2011

Brandes, Philipp; Degener, Bastian; Kempkes, Barbara; Meyer auf der Heide, Friedhelm: Energy-efficient strategies for building short chains of mobile robots locally. In: Proceedings of the 18th International Colloquium on Structural Information and Communication Complexity (SIROCCO'11), pp. 138-149, 2011

Briest, Patrick; Raupach, Christoph: The Car Sharing Problem. In: Proceedings of the 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'11), 2011

Briest, Patrick; Hoefer, Martin; Krysta, Piotr: Stackelberg Network Pricing Games. Algorithmica, 2011

Degener, Bastian; Kempkes, Barbara; Meyer auf der Heide, Friedhelm: Organic Computing — A Paradigm Shift for Complex Systems, Autonomic Systems, volume 1, chapter Energy-Awareness in Self-organising Robotic Exploration Teams, pp. 531-543, Springer Verlag, 2011

Briest, Patrick; Krysta, Piotr: Buying Cheap is Expensive: Approximability of Combinatorial Pricing Problems. SIAM Journal on Computing, 2011

Klaas, Alexander; Laroque, Christoph; Renken, Hendrik; Dangelmaier, Wilhelm: Goal-Based Agents in Material Flow Simulations - Integration of an Agent Programming Framework in the Discrete Event Simulator D3FACT. In: Proceedings of The 25th European Simulation and Modelling Conference (ESM'11), 2011

Briest, Patrick; Krysta, Piotr; Vöcking, Berthold: Approximation Techniques for Utilitarian Mechanism Design. SIAM Journal on Computing, 2011

 

PhD Theses

Joachim Gehweiler:
Peer-to-Peer Based Parallel Web Computing
Web computing is a variant of parallel computing where the idle times of PCs donated by worldwide distributed users are employed to execute parallel programs. In this thesis we consider a web computing variant with two important properties: First, we support the execution of coupled, massively parallel algorithms (rather than distributed data processing). And second, we organize the system in peer-to-peer fashion.We present the Paderborn University BSP-based Web Computing (PUB-Web) library, which supports the execution of parallel programs in the bulk-synchronous style (BSP) in such a web computing setting. In this thesis, we focus on important technical and algorithmic aspects, in particular: In order to schedule processes with respect to the currently available computing power, which continually changes in an unpredictable fashion, we need intelligent load balancing algorithms and as a basic precondition the technical ability to migrate threads at runtime.To achieve the latter, we present the PadMig thread migration and checkpointing library. In order to tackle the distributed load balancing problem, we present an algorithm based on Distributed Heterogeneous Hash-Tables. In order to judge the quality of the schedules produced, we perform extensive experiments. Beside the available computing power, we finally also consider the network bandwidth as a secondary criterion for load balancing.

Sascha Effert:
Verfahren zur redundanten Datenplatzierung in skalierbaren Speichersystemen
Moderne Datenzentren sind mit einer rasant wachsenden Menge an Daten konfrontiert, welche sie mit immer höherer Geschwindigkeit hochverfügbar speichern müssen. Daher brauchen sie Speichersysteme, welche mit ihren Anforderungen wachsen. Zunehmend werden dazu Speichernetze eingesetzt, in welchen Datenserver einen virtuellen Speicher über Festplatten erzeugen. Dabei ist die Last des virtuellen Speichers so zu verteilen, dass die physikalischen Festplatten optimal genutzt werden. Um Ausfälle kompensieren zu können ist es nötig, Daten redundant zu speichern. Die Verfahren zur Datenverteilung müssen diesen Anforderungen gerecht werden. Einen wichtigen Beitrag liefern hier pseudorandomisierte Hashfunktionen. Innerhalb dieser Arbeit gehe ich auf verschiedene Speichersysteme ein. Speziell untersuche ich Speichernetze, welche aus Datenservern mit lokalen Festplatten bestehen. Für diese zeige ich, wie sie bei verschiedenen Arten der Datenverteilung skalieren. Leider wird keines der betrachteten Speichersysteme allen Anforderungen gerecht. Als Lösung stelle ich das Verfahren Redundant Share vor, welches alle Anforderungen erfüllt. Mittels Redundant Share kann eine beliebige Anzahl an Kopien der Daten des virtuellen Speichers wie gefordert verteilt werden. Gleichzeitig erfordert das Hinzufügen neuer Festplatten einen begrenzten Aufwand. Abschließend vermesse ich eine Implementierung von Redundant Share und vergleiche die Ergebnisse mit anderen Verteilern.

Additional Functions

Friedhelm 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“
  • DFG Special Advisor (Vertrauensdozent) of the University of Paderborn
  • Member of the Board of External Scientific Advisers (Fachbeirat) of the Max-Planck-Institute for Computer Science at Saarbrücken
  • Direktor der 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
  • Member of the program committee of the workshop “Parallele Algorithmen, Rechnerstrukturen und Systemsoftware (PARS)“, 2011
  • Member of the Evaluation Committee of the Bundeswettbewerb “Jugend Forscht“, Coordinator of the section on Computer Science and Mathematics.
  • General Chair of the ACM-Symposium “Parallelism in Algorithms and Architectures (SPAA)“
  • Member of the Award Committee of the European Association for Theoretical Computer Science (EATCS)

Patrick Briest:

  • Member of the program committee of the "ACM Conference on Electronic Commerce (EC)", 2011.
  • Member of the program committee of the "International Symposium on Theoretical Aspects of Computer Science (STACS)", 2011.

School Programs

  • International Graduate School: NRW Graduate School of Dynamic Intelligent Systems
  • GSANS - the Paderborn Graduate School on Applied Network Science
  • 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“ 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.-Ing.  André Brinkmann, Prof. Dr. Marco Platzner), and Z (Central Duties of the CRC)

FRONTS:

EU-Strep “Foundations of Adaptive Networked Societies of Tiny Artefacts“

DFG-SmartTeams:

DFG-Schwerpunktprogramm 1183 „Organic Computing“ mit dem Projekt: „Smart Teams“ (zusammen mit Prof. Dr. rer. nat. Christian Schindelhauer, Freiburg)

DFG-AVIPASIA:

DFG project “Interactive Model Modification, Synchronized Analysis and 3D Visualization of Parallel Discrete Event Simulation“ (with Prof. Dr.-Ing. habil. Wilhelm Dangelmaier and Dr. rer. nat. Matthias Fischer)

Our Activities 2010

Publications

Cord-Landwehr, Andreas; Degener, Bastian; Fischer, Matthias; Hüllmann, Martina; Kempkes, Barbara; Klaas, Alexander; Kling, Peter; Kurras, Sven; Märtens, Marcus; Meyer auf der Heide, Friedhelm; Raupach, Christoph; Swierkot, Kamil; Warner, Daniel; Weddemann, Christoph; Wonisch, Daniel: Collision-less gathering of robots with an extent. In: 37th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2011), 22. - 28. Jan. 2011, Springer

Janson, Thomas; Mahlmann, Peter; Schindelhauer, Christian: A Self-Stabilizing Locality-Aware Peer-to-Peer Network Combining Random Networks, Search Trees, and DHTs. In: Proceedings of the 16th International Conference on Parallel and Distributed Systems (ICPADS’10), Shanghai, China, 9. - 10. Dez. 2010, IEEE

Suess, Tim; Wiesemann, Timo; Fischer, Matthias: Evaluation of a c-Load-Collision-Protocol for Load-Balancing in Interactive Environments. In: 5th IEEE International Conference on Networking, Architecture, and Storage, S. 448 - 456, 15. - 17. Jul. 2010 IEEE Computer Society, IEEE Press

Dumrauf, Dominic; Suess, Tim: On the Complexity of Local Search for Weighted Standard Set Problems. In: Proc. 6th Conference on Computability in Europe, S. 132-140, 30. Jun. - 4. Jul. 2010

Abramsky, Samson ; Gavoille, Cyril ; Kirchner, Claude ; Meyer auf der Heide, Friedhelm; Spirakis, Paul G. (Hrsg.) 37th International Colloquium on Automata, Languages and Programming (ICALP 2010) Part I. LNCS, Band 6198, Bordeaux, France, Jul. 2010, Springer

Abramsky, Samson ; Gavoille, Cyril ; Kirchner, Claude ; Meyer auf der Heide, Friedhelm; Spirakis, Paul G. (Hrsg.) 37th International Colloquium on Automata, Languages and Programming (ICALP 2010) Part II. LNCS, Band 6199, Bordeaux, France, Jul. 2010, Springer

Degener, Bastian; Gehweiler, Joachim; Lammersen, Christiane: Kinetic Facility Location. Algorithmica, 57(3): S. 562-584, Jul. 2010

Degener, Bastian; Kempkes, Barbara; Kling, Peter; Meyer auf der Heide, Friedhelm: A continuous, local strategy for constructing a short chain of mobile robots. In: SIROCCO '10: Proceedings of the 17th International Colloquium on Structural Information and Communication Complexity, LNCS, Band 6058, S. 168-182, 7. - 11. Jun. 2010, Springer

Meyer auf der Heide, Friedhelm; Phillips, Cynthia (Hrsg.) SPAA 2010: Proceedings of the 22nd Annual ACM Symposium on Parallelism in Algorithms and Architectures. , Thira, Santorini, Greece, Jun. 2010, ACM Press

Degener, Bastian; Kempkes, Barbara; Meyer auf der Heide, Friedhelm: A local O(n²) gathering algorithm. In: SPAA 2010: Proceedings of the 22nd Annual ACM Symposium on Parallelism in Algorithms and Architectures, S. 217-223, Jun. 2010, ACM

Suess, Tim; Jaehn, Claudius; Fischer, Matthias: Asynchronous Parallel Reliefboard Computation for Scene Object Approximation. In: Eurographics Symposium on Parallel Graphics and Visualization (EGPGV), S. 43-51, Norrköping, Sweden, Mai 2010 Eurographics Association, Eurographics Association

Mense, Mario; Schindelhauer, Christian: Read-Write-Codes: An Erasure Resilient Encoding System for Flexible Reading and Writing in Storage Networks. In: Proceedings of 11th International Symposium on Stabilization, Safety, and Security of Distributed Systems, Lecture Notes in Computer Science, Band 5873, S. 624--639, 2010, Springer

Degener, Bastian; Kempkes, Barbara; Pietrzyk, Peter: A local, distributed constant-factor approximation algorithm for the dynamic facility location problem . In: International Parallel & Distributed Processing Symposium (IPDPS), 2010

Fischer, Matthias; Renken, Hendrik; Laroque, Christoph; Schaumann, Guido; Dangelmaier, Wilhelm: Automated 3D-Motion Planning for Ramps and Stairs in Intra-Logistics Material Flow Simulations. In: Proceedings of the 2010 Winter Simulation Conference (WSC 2010), S. 1648 - 1660, 5. - 8. Dez. 2010 IEEE, Omnipress

Damerow, Valentina; Manthey, Bodo; Meyer auf der Heide, Friedhelm; Räcke, Harald; Scheideler, Christian; Sohler, Christian; Tantau, Till: Smoothed Analysis of Left-To-Right Maxima with Applications. akzeptiert in: ACM Transactions on Algorithms 2010

Briest, Patrick; Chalermsook, Parinya; Khanna, Sanjeev; Laekhanukit, Bundit; Nanongkai, Danupon: Improved Hardness of Approximation for Stackelberg Shortest-Path Pricing. In: Workshop on Internet and Network Economics (WINE), 2010 (Details)

Briest, Patrick; Röglin, Heiko: The Power of Uncertainty: Bundle-Pricing for Unit-Demand Customers. In: Workshop on Approximation and Online Algorithms (WAOA), 2010 (Details)

Briest, Patrick; Chawla, Shuchi; Kleinberg, Robert D.; Weinberg, S. Matthew: Pricing Randomized Allocations. In: Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA), 2010

Gehweiler, Joachim; Meyerhenke, Henning: A Distributed Diffusive Heuristic for Clustering a Virtual P2P Supercomputer. In: Proceedings of 24th International Parallel and Distributed Processing Symposium (IPDPS, HPGC), 2010

Meyer auf der Heide, Friedhelm; Scheideler, Christian: Algorithmische Grundlagen verteilter Speichersysteme. Informatik-Spektrum, 33(5): S. 468-474 2010

Degener, Bastian; Fekete, Sándor; Kempkes, Barbara; Meyer auf der Heide, Friedhelm: A survey on relay placement with runtime and approximation guarantees. Computer Science Review 2010

Gehweiler, Joachim; Meyer auf der Heide, Friedhelm: Bin Packing - How Do I Get My Stuff into the Boxes?. In: Algorithms Unplugged, Springer, 2010

Eikel, Benjamin; Jaehn, Claudius; Fischer, Matthias: Preprocessed Global Visibility for Real-Time Rendering on Low-End Hardware. In: Advances in Visual Computing, Lecture Notes in Computer Science, Band 6453, S. 622--633. Springer, Berlin / Heidelberg, 2010

Suess, Tim; Wiesemann, Timo; Fischer, Matthias: Gewichtetes c-Collision-Protokoll zur Balancierung eines parallelen Out-of-Core-Renderingsystems. In: Augmented & Virtual Reality in der Produktentstehung, S. 39-52, 2010 Universität Paderborn, HNI Verlagsschriftenreihe

Meyerhenke, Henning; Gehweiler, Joachim: On Dynamic Graph Partitioning and Graph Clustering using Diffusion. In: Dagstuhl Seminar Proceedings 10261: Algorithm Engineering, 2010

 

PhD Theses

Dr. rer. nat. Jan Mehler:
Power-aware online file allocation in dynamic networks
The availability of both mobile networks composed of wireless gadgets (e.g. smartphones and PDAs) and wireless sensor networks currently increases significantly. A basic requirement for the operation of such mobile ad hoc networks is a service which enables the network nodes to share common data. The "file allocation problem'' introduced by Bartal assumes that a data management system is able to create and remove arbitrary many copies of a data file on the nodes of the network as and when required. Since the nodes of a mobile ad hoc network usually have only a limited amount of energy, our goal is to find algorithms which minimize the energy consumption of the nodes while serving a sequence of read- and write-requests issued by the nodes. To achieve this, an algorithm has to create and remove copies in such a way that on the one hand read-requests can be fulfilled by nearby nodes and on the other hand updating all the copies on a write-request is not too expensive. We generalize Bartal's file allocation problem to dynamic networks, i.e. the weights of the edges are changing over time. A major challenge thereby is that an algorithm knows neither which nodes issue what kind of requests beforehand nor how the network changes in the future. We analyze the quality of different online algorithms for the file allocation problem in dynamic networks using theoretical and simulation based methods.

Dr. rer. nat. Peter Mahlmann:
Peer-to-peer networks based on random graphs
Peer-to-peer networks belong to the class of overlay networks, i.e. the network is built on top of a physical network (e.g. the Internet) which is used to realize the communication between the nodes (peers) of the overlay. In contrast to the nodes in a client server architecture, peers have symmetric functionality: every peer acts as a server as well as a client. This property bears the potential of excellent resilience to network failures, since a faulty peer can be replaced by every other peer in the network. Studies of real world peer-to-peer networks reveal that these are highly dynamic. Thus, it is of major importance to take advantage of the potential robustness when designing a peer-to-peer network and it is reasonable to choose a simple network structure that can be maintained in case of strong dynamics and therefore guarantees the functionality of the network. This criterion is met by random networks. In this thesis we present local graph transformations to build and maintain random networks without central coordination mechanisms. They especially allow to maintain properties such as logarithmic diameter and expansion by local ``handshake'' operations only and are able to recover from any worst case situation. To overcome the lack of efficient query algorithms for random networks, we describe how to use random networks as a building block of a structured peer-to-peer network. For this, we cleverly combine random networks, search trees, and distributed hash tables to overcome their individual shortcomings while keeping their individual strength. The resulting network, called 3nuts, is self-stabilizing and load-balanced, supports range queries, and allows routing with small latency by adapting the structure of the overlay to the underlying physical network.

Dr. rer. nat. Sebastian Degener:
Local, distributed approximation algorithms for geometric assignment problems
We consider a group of autonomous robots that is deployed to an unknown terrain. There is no central control and the robots have to organize themselves. The central challenge is that each robot senses only its direct neighborhood and is only able to communicate with robots in its direct neighborhood. This leads to many algorithmic challenges. In this thesis we study, how task assignment problems can be solved in such a scenario, such that despite the locality constraints provable globally good solution are computed. In the first part of the thesis robots are assigned to treasures that are found in the terrain. In the second part of the thesis, roles within the robot team are dynamically assigned to robots. Those assignments have to be changed over time, since the robots move. In both parts, lower bounds are shown, as well as local approximation algorithms are described and analyzed.

Additional Functions

Friedhelm Meyer auf der Heide:

  • Member of the “Hochschulrat“ of the University of Paderborn
  • Member of the German Academy of Sciences „Leopoldina“
  • DFG Special Advisor (Vertrauensdozent) of the University of Paderborn
  • Member of the Board of External Scientific Advisers (Fachbeirat) of the Max-Planck-Institute for Computer Science at Saarbrücken
  • Direktor der NRW-Graduate School of Dynamic Intelligent Systems (one of three directors)
  • Assistant Chairman of the Paderborn Institute for Scientific Computation (PaSCo) and its graduate college
  • Managing Editor of “Journal of Interconnection Networks (JOIN)“, World Scientific Publishing
  • Member of the program committee of the workshop „Parallele Algorithmen, Rechnerstrukturen und Systemsoftware (PARS)“, 2009
  • Member of the program committee of the „Algorithms and Data Structures Symposium (WADS)“, 2009
  • Member of the program committee of the “International Symposium on Mathematical Foundations of Computer Science (MFCS)“, 2009
  • Member of the Evaluation Committee of the “Bundeswettbewerb “Jugend Forscht“, Coordinator of the section on Computer Science and Mathematics.
  • General Chair of the ACM-Symposiums „Parallelism in Algorithms and Architectures (SPAA)“ Graduate

Patrick Briest:

  • Member of the program committee of the "International Symposium on Theoretical Aspects of Computer Science (STACS) ", 2011.

School Programs:

  • International Graduate School: NRW Graduate School of Dynamic Intelligent Systems
  • Pasco-GK: DFG Research Training Centre (postgraduate program) "Scientific Computation"
  • DFG Research Training Centre "Automatisms - emerging structures in information technology, media, and culture"

Current Research Projects

AEOLUS: EU-Integrated Project IST-15964 „Algorithmic Principles for Building Efficient Overlay Computers“ (AEOLUS)

FRONTS: EU-Strep „Foundations of Adaptive Networked Societies of Tiny Artefacts“

DFG-Smart Teams: DFG Priority Program 1183 „Organic Computing“ with the project: „Smart Teams“ (with Prof. Dr. rer. nat. Christian Schindelhauer)

DFG-AlgoEngCG: DFG Priority Program 1307 „Algorithm Engineering“ with the project: „ Algorithm Engineering for Problems in Computer Graphics “ (with Dr. rer. nat. Matthias Fischer)

DFG-AVIPASIA: DFG project „Interactive Model Modification, Synchronized Analysis and 3D Visualization of Parallel Discrete Event Simulation“ (with Prof. Dr.- Ing. habil. Wilhelm Dangelmaier and Dr. rer. nat. Matthias Fischer)

ViProSim: Center of excellence “Distributed Visualization and Simulation“ (VisSim). Agreement on objectives of University of Paderborn and Ministry for Science and Research of North Rhine-Westphalia