Local Approximation Algorithms for the Uncapacitated Metric Facility Location Problem in Power-Aware Sensor Networks - Abshoff, Sebastan; Cord-Landwehr, Andreas; Degener, Bastian; Kempkes, Barbara; Pietrzyk, Peter (Proceedings of the 7th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities (ALGOSENSORS))
We present two distributed, constant factor approximation algorithms for the metric facility location problem. Both algorithms have been designed with a strong emphasis on applicability in the area of wireless sensor networks: in order to execute them, each sensor node only requires limited local knowledge and simple computations. Also, the algorithms can cope with measurement errors and take into account that communication costs between sensor nodes do not necessarily increase linearly with the distance, but can be represented by a polynomial. Since it cannot always be expected that sensor nodes execute algorithms in a synchronized way, our algorithms are executed in an asynchronous model (but they are still able to break symmetry that might occur when two neighboring nodes act at exactly the same time). Furthermore, they can deal with dynamic scenarios: if a node moves, the solution is updated and the update affects only nodes in the local neighborhood. Finally, the algorithms are robust in the sense that incorrect behavior of some nodes during some round will, in the end, still result in a good approximation. The first algorithm runs in expected O(log_{1+ε} n) communication rounds and yields a \my^4(1+4\my^2(1+ε)^{1/p})^p approximation, while the second has a running time of expected O(log^2_{1+ε} n) communication rounds and an approximation factor of \my^4(1 + 2(1 + ε)^{1/p})^p. Here, ε > 0 is an arbitrarily small constant, p the exponent of the polynomial representing the communication costs, and \my the relative measurement error.

Complexity Classes for Local Computation - Swierkot, Kamil

An Experimental Comparison of Load Balancing Strategies in a Web Computing Environment - Gehweiler, Joachim; Kling, Peter; Meyer auf der Heide, Friedhelm (Proceedings of the 9th International Conference on Parallel Processing and Applied Mathematics (PPAM))
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. The PUB-Web library developed by us supports this kind of usage of computing resources. A major problem for the efficient execution of such parallel programs is load balancing. In the Web Computing context, this problem becomes more difficult because of the dynamic behavior of the underlying "parallel computer": the set of available processors (donated PCs) as well as their availability (idle times) change over time in an unpredictable fashion.In this paper, we experimentally evaluate and compare load balancing algorithms in this scenario, namely a variant of the well-established Work Stealing algorithm and strategies based on a heterogeneous version of distributed hash-tables (DHHTs) introduced recently. In order to run a meaningful experimental evaluation, we employ, in addition to our Web Computing library PUB-Web, realistic data sets for the job input streams and for the dynamics of the availability of the resources.Our experimental evaluations suggest that Work Stealing is the better strategy if the number of processes ready to run matches the number of available processors. But a suitable variant of DHHTs outperforms Work Stealing if there are significantly more processes ready to run than available processors.

23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures

Collisionless Gathering of Robots with an Extent - 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; et al. (37th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2011))
Gathering n mobile robots in one single point in the Euclidean plane is a widely studied problem from the area of robot formation problems. Classically, the robots are assumed to have no physical extent, and they are able to share a position with other robots. We drop these assumptions and investigate a similar problem for robots with (a spherical) extent: the goal is to gather the robots as close together as possible. More exactly, we want the robots to form a sphere with minimum radius around a predefined point. We propose an algorithm for this problem which synchronously moves the robots towards the center of the sphere unless they block each other. In this case, if possible, the robots spin around the center of the sphere. We analyze this algorithm experimentally in the plane. If R is the distance of the farthest robot to the center of the sphere, the simulations indicate a runtime which is linear in n and R. Additionally, we prove a theoretic upper bound for the runtime of O(nR) for a discrete version of the problem. Simulations also suggest a runtime of O(n + R) for the discrete version.

Bin Packing - How Do I Get My Stuff into the Boxes - Gehweiler, Joachim; Meyer auf der Heide, Friedhelm (Algorithms Unplugged)

Proceedings of the 23rd ACM symposium on Parallelism in algorithms and architectures - SPAA '11 - Rajaraman, Rajmohan; Meyer auf der Heide, Friedhelm

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

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

A tight runtime bound for synchronous gathering of autonomous robots with limited visibility - Degener, Bastian; Kempkes, Barbara; Langner, Tobias; Meyer auf der Heide, Friedhelm; Pietrzyk, Peter; Wattenhofer, Roger (Proceedings of the 23rd ACM symposium on Parallelism in algorithms and architectures - SPAA '11)