Two different approaches to a macroscopic model of a bio-inspired robotic swarm - Schmickl, Thomas; Hamann, Heiko; Wörn, Heinz; Crailsheim, Karl (Robotics and Autonomous Systems)
By compiling macroscopic models we analyze the adaptive behavior in a swarm of autonomous robots generated by a bio-inspired, distributed control algorithm. We developed two macroscopic models by taking two different perspectives: A Stock & Flow model, which is simple to implement and fast to simulate, and a spatially resolved model based on diffusion processes. These two models were compared concerning their prediction quality and their analytical power: One model allowed easy identification of the major feedback loops governing the swarm behavior. The other model allowed analysis of the expected shapes and positions of observable robot clusters. We found a high correlation in the challenges posed by both modeling techniques and we highlighted the inherent problems of inferring emergent macroscopic rules from a microscopic description of swarm behavior.

Pattern Formation as a Transient Phenomenon in the Nonlinear Dynamics of a Multi-Agent System - Hamann, Heiko; Troch, Inge; Breitenecker, F. (MATHMOD 2009 - 6th Vienna International Conference on Mathematical Modelling)

Self-Organisation and Self-Optimization - Meyer auf der Heide, Friedhelm; Rammig, Franz-Josef (Public Service Review: Science and Technology)

Algorithmische und komplexitätstheoretische Aspekte kombinatorischer Preisoptimierung (Computational Aspects of Combinatorial Pricing Problems) - Briest, Patrick (it - Information Technology)

On Stackelberg Pricing with Computationally Bounded Consumers - Briest, Patrick; Hoefer, Martin; Gualà, Luciano; Ventre, Carmine (Lecture Notes in Computer Science)
In a Stackelberg pricing game a leader aims to set prices on a subset of a given collection of items, such as to maximize her revenue from a follower purchasing a feasible subset of the items. We focus on the case of computationally bounded followers who cannot optimize exactly over the range of all feasible subsets, but apply some publicly known algorithm to determine the set of items to purchase. This corresponds to general multi-dimensional pricing assuming that consumers cannot optimize over the full domain of their valuation functions but still aim to act rationally to the best of their ability. We consider two versions of this novel type of Stackelberg pricing games. Assuming that items are weighted objects and the follower seeks to purchase a min-cost selection of objects of some minimum weight (the Min-Knapsack problem) and uses a simple greedy 2-approximate algorithm, we show how an extension of the known single-price algorithm can be used to derive a polynomial-time (2 + ε)-approximation algorithm for the leader’s revenue maximization problem based on so-called near-uniform price assignments. We also prove the problem to be strongly NP-hard. Considering the case that items are subsets of some ground set which the follower seeks to cover (the Set-Cover problem) via a standard primal-dual approach, we prove that near-uniform price assignments fail to yield a good approximation guarantee. However, in the special case of elements with frequency 2 (the Vertex-Cover problem) it turns out that exact revenue maximization can be done in polynomial-time. This stands in sharp contrast to the fact that revenue maximization becomes APX-hard already for elements with frequency 3.

Concepts for Model Verification and Validation during Simulation Runtime - Laroque, Christoph; Fischer, Matthias; Dangelmaier, Wilhelm (European Simulation and Modelling Conference (ESM 2009))
Modern companies are nowadays confronted with an increasing demand of multiple products, where they need to perform more flexible every day. Cost-intensive decisions are to be confirmed in short times, in order to minimize risks and secure efficient production programs as well as material flows. Tools for this digital planning via simulation methods are one well established possibility to receive decision support. Nevertheless, the creation of the necessary simulation models is a complicated and error-prone process, where complexity of modeling, validation and verification depends on the used tool and its functionalities. This paper presents implemented concepts for an innovative user support in his tasks of verification and validation of simulation models during the execution of a simulation run. Time-intensive procedures like stopping simulation, parameterization and restarting within the problem analysis are simplified. So the user is able to focus on the real problem solving task.

Ein System zur aggregierten Visualisierung verteilter Materialflusssimulationen - Suess, Tim; Fischer, Matthias; Huber, Daniel; Laroque, Christoph; Dangelmaier, Wilhelm (Augmented & Virtual Reality in der Produktentstehung)

Planar Visibility Counting - Fischer, Matthias; Hilbig, Matthias; Jähn, Claudius; Meyer auf der Heide, Friedhelm; Ziegler, Martin (Proc. 25th European Workshop on Computational Geometry)
For a fixed virtual scene (=collection of simplices) S and given observer position p, how many elements of S are weakly visible (i.e. not fully occluded by others) from p? The present work explores the trade-off between query time and preprocessing space for these quantities in 2D: exactly, in the approximate deterministic, and in the probabilistic sense. We deduce the EXISTENCE of an O(m^2/n^2) space data structure for S that, given p and time O(log n), allows to approximate the ratio of occluded segments up to arbitrary constant absolute error; here m denotes the size of the Visibility Graph--which may be quadratic, but typically is just linear in the size n of the scene S. On the other hand, we present a data structure CONSTRUCTIBLE in O(n*log(n)+m^2*polylog(n)/k) preprocessing time and space with similar approximation properties and query time O(k*polylog n), where k<n is an arbitrary parameter. We describe an implementation of this approach and demonstrate the practical benefit of the parameter k to trade memory for query time in an empirical evaluation on three classes of benchmark scenes.

Optimal strategies for maintaining a chain of relays between an explorer and a base camp - Kutyłowski, Jarosław; Meyer auf der Heide, Friedhelm (Theoretical Computer Science)

Power-aware online file allocation in mobile ad hoc networks - Mehler, Jan; Meyer auf der Heide, Friedhelm (Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures - SPAA '09)

Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures - SPAA '09

Optimal algorithms for page migration in dynamic networks - Bienkowski, Marcin; Byrka, Jaroslaw; Korzeniowski, Miroslaw; Meyer auf der Heide, Friedhelm (Journal of Discrete Algorithms)

Distributed Resource Allocation and Management in Heterogeneous Networks - Schomaker, Gunnar

Uniform Budgets and the Envy-Free Pricing Problem - Briest, Patrick (Proceedings of the 35th InternationalColloquium on Automata, Languages and Programming (ICALP))

On the Approximability of Combinatorial Exchange Problems - Briest, Patrick; Krysta, Piotr; Babaioff, Moshe (Proceedings of the 1st International Symposium on Algorithmic Game Theory (SAGT))

Approximate Equilibria in Games with Few Players - Briest, Patrick; Goldberg, Paul W.; Roeglin, Heiko
We study the problem of computing approximate Nash equilibria (epsilon-Nash equilibria) in normal form games, where the number of players is a small constant. We consider the approach of looking for solutions with constant support size. It is known from recent work that in the 2-player case, a 1/2-Nash equilibrium can be easily found, but in general one cannot achieve a smaller value of epsilon than 1/2. In this paper we extend those results to the k-player case, and find that epsilon = 1-1/k is feasible, but cannot be improved upon. We show how stronger results for the 2-player case may be used in order to slightly improve upon the epsilon = 1-1/k obtained in the k-player case.

Random Graphs for Peer-to-Peer Overlays - Schindelhauer, Christian; Mahlmann, Peter (The European Integrated Project "Dynamically Evolving, Large Scale Information Systems (DELIS), Proceedings of the Final Workshop)
Modern peer-to-peer networks consist of several network layers and distributed algorithms providing features like indexing, resource balancing, entry protocols, security, anonymity, and cryptography. Since peer-to-peer networks are highly dynamic, a fundamental task in the design of these networks is to provide high connectivity. We propose a solution by distributed random link exchange algorithms such that the overlay network can be a connected random graph or use a random graph as backbone. Random graphs are expander graphs have logarithmic diameter, high node connectivity, excellent communication properties, and are expander graphs with high probability. In summary: they are an excellent choice to improve the stability and robustness of a dynamic network.

Detours Save Energy in Mobile Wireless Networks - Ooi, Chia Ching; Schindelhauer, Christian (MWCN'08: Proc. of IFIP Joint Conference on Mobile Wireless Communications Networks (MWCN 2008) and Personal Wireless Communications (PWC 2008))
Autonomous robotic systems have been gaining the attention of research community in mobile ad hoc network since the past few years. While motion cost and communications cost constitute the primary energy consumers, each of them is investigated independently. By taking into account the power consumption of both entities, the overall energy efficiency of a system can be further improved. In this paper, the energy optimization problem of radio communication and motion is examined. We consider a hybrid wireless network that consists of a single autonomous mobile node and multiple relay nodes. The mobile node interacts with the relays within its vicinity by continuously communicating high-bandwidth data, e.g. triggered by a multimedia application like video surveillance. The goal is to find the best path such that the energy consumption for both mobility and communications is minimized. We introduce the Radio-Energy-Aware (REA) path computation strategy by utilizing node mobility. Given the starting point, the target point and the position of the relays, our simulation results show that the proposed strategy improves the energy efficiency of mobile node compared to the Motion-Energy-Aware (MEA) path constructed based only on the mobility cost.

Energy-Efficient Distributed Target Tracking Using Wireless Relay Robots - Ooi, Chia Ching; Schindelhauer, Christian (ARS'08: Proc. of the 9th International Symposium on Distributed Autonomous Robotic Systems (DARS 2008))

Lokale Strategien zur Optimierung von Kommunikationsketten - Pietrzyk, Peter

Space-Time Continuous Models of Swarm Robotic Systems - Hamann, Heiko

Kolmogorov Complexity Theory over the Reals - Ziegler, Martin; Koolen, Wouter M. (arXiv:0802.2027)
Kolmogorov Complexity constitutes an integral part of computability theory, information theory, and computational complexity theory -- in the discrete setting of bits and Turing machines. Over real numbers, on the other hand, the BSS-machine (aka real-RAM) has been established as a major model of computation. This real realm has turned out to exhibit natural counterparts to many notions and results in classical complexity and recursion theory; although usually with considerably different proofs. The present work investigates similarities and differences between discrete and real Kolmogorov Complexity as introduced by Montana and Pardo (1998).

On the Stability of Fast Polynomial Arithmetic - Köhler, Sven; Ziegler, Martin (Proc. 8th Conference on Real Numbers and Computers)
Operations on univariate dense polynomials—multiplication, division with remainder, multipoint evaluation—constitute central primitives entering as build-up blocks into many higher applications and algorithms. Fast Fourier Transform permits to accelerate them from naive quadratic to running time O(n·polylogn), that is softly linear in the degree n of the input. This is routinely employed in complexity theoretic considerations and, over integers and finite fields, in practical number theoretic calculations. The present work explores the benefit of fast polynomial arithmetic over the field of real numbers where the precision of approximation becomes crucial. To this end, we study the computability of the above operations in the sense of Recursive Analysis as an effective refinement of continuity. This theo- retical worst-case stability analysis is then complemented by an empirical evaluation: We use GMP and the iRRAM to find the precision required for the intermediate calculations in order to achieve a desired output accuracy.

Physically-Relativized Church-Turing Hypotheses - Ziegler, Martin (Applied Mathematics and Computation)
We turn the physical Church-Turing Hypothesis from an ambiguous source of sensational speculations into a (collection of) sound and well-defined scientific problem(s): Examining recent controversies and causes for misunderstanding concerning the state of the Church- Turing Hypothesis (CTH), it is suggested to study the CTH ‘sharpened’ relative to an arbitrary but specific physical theory—rather than vaguely referring to “nature” in general. For this purpose we combine physical structuralism with computational complexity theory. The benefits of this approach are illustrated by some exemplary results on computability and complexity in computational physics.

A Meta-Theory of Physics and Computation - Ziegler, Martin (Verhandlungen der Deutschen Physikalischen Gesellschaft)

An explicit solution to Post's Problem over the reals - Meer, Klaus; Ziegler, Martin (Journal of Complexity)

A System for Aggregated Visualization of Multiple Parallel Discrete Event Simulations - Suess, Tim; Huber, Daniel; Fischer, Matthias; Laroque, Christoph; Dangelmaier, Wilhelm (IEEE International Symposium on Parallel and Distributed Processing with Applications)
In this paper we present a system for the simultaneous visualization of several parallel executed simulation replications. By aggregating the scenes of multiple similar simulations into one single scene it is possible to make a visual statistical analysis of a set of discrete event simulations as well as to easily compare different system parameterizations. The aim of our system is to enhance the model analysis, verification and validation process in terms of speed and ease. The parallel execution of several simulations of complex models and the visualization of these cannot be done on one computer, thus a parallel approach is necessary. Our system uses a thin-client and multiple processors on a PC-cluster. The rendering and the simulation execution are done on processors of the cluster. The client is used only for the visualization of the images transmitted by the cluster and for user interaction.

The European Integrated Project "Dynamically Evolving, Large Scale Information Systems (DELIS) - Meyer auf der Heide, Friedhelm

Aggregated 3D-visualization of a distributed simulation experiment of a queuing system - Dangelmaier, Wilhelm; Fischer, Matthias; Huber, Daniel; Laroque, Christoph; Suess, Tim (2008 Winter Simulation Conference)
The paper describes an approach for an aggregated animation of a simulation experiment in an interactive 3D environment, visualizing multiple, distributed simulation runs. Although the general approach of a 3-dimensional visualization of material flow simulation helps to understand the dynamic behavior of a system better as well as faster, it remains unclear, how typical the animated simulation represents the model, if there is a stochastic influence for even some parameters. By the integrated visualization of multiple distributed simulation runs, this uncertainty can be solved, which will be shown in this paper for a typical simulation study of a queuing system.

The Kinetic Facility Location Problem - Degener, Bastian; Gehweiler, Joachim; Lammersen, Christiane (Proceedings of the 11th Scandinavian Workshop on Algorithm Theory (SWAT))

The Kinetic Facility Location Problem - Gehweiler, Joachim; Lammersen, Christiane; Degener, Bastian (Proceedings of the 24th European Workshop on Computational Geometry)
We present a deterministic kinetic data structure for the facility location problem that maintains a subset of the moving points as facilities such that, at any point of time, the sum of the maintenance cost for the facilities and the connection cost for the clients is at most a constant factor larger than the current optimal cost. In our scenario, each point can open a facility and moves continuously along a known trajectory in a d-dimensional Euclidean space where d is a constant. Our kinetic data structure has a storage requirement of O(n (log^d(n)+log(nR))), where n is the number of points and R is the ratio of the product of the maximum maintenance cost and demand to the product of their corresponding minimum values. In the case that each trajectory can be described by a bounded degree polynomial, the data structure processes O(n^2 log^2(nR)) events, each requiring only O(log(nR)) facility changes and O(log^(d+1)(n) log(nR)) time. This results in a total processing time of O(n^2 log^(d+1)(n) log^3(nR)). To the best of our knowledge, this is the first kinetic data structure for the facility location problem.

SPREAD: an adaptive scheme for redundant and fair storage in dynamic heterogeneous storage systems - Mense, Mario; Scheideler, Christian (Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20-22, 2008)

Aggregating Robots Compute: An Adaptive Heuristic for the Euclidean Steiner Tree Problem - Hamann, Heiko; Wörn, Heinz (The tenth International Conference on Simulation of Adaptive Behavior (SAB'08))

Spatial Macroscopic Models of a Bio-Inspired Robotic Swarm Algorithm - Hamann, Heiko; Schmickl, Thomas; Wörn, Heinz; Crailsheim, Karl (IEEE/RSJ 2008 International Conference on Intelligent Robots and Systems (IROS'08))
We present a comparative study of two spatially resolved macroscopic models of an autonomous robotic swarm. In previous experiments, the collective behavior of 15 autonomous swarm robots, driven by a simple bio-inspired control algorithm, was investigated: in two different environmental conditions, the ability of the robots to aggregate below a light source was tested. Distinct approaches to predict the dynamics of the spatial distribution were made by two different modeling approaches: one model was constructed in a compartmental manner (ODEs). In parallel, a space-continuous model (PDEs) was constructed. Both models show a high degree of similarity concerning the modeling of concrete environmental factors (light), but due to their different basic approaches, show also significant differences in their implementation. However, the predictions of both models compare well to the observed behavior of the robotic swarm, thus both models can be used to develop further extensions of the algorithm as well as different experimental setups without the need to run extensive real robotic preliminary experiments.

A framework of space–time continuous models for algorithm design in swarm robotics - Hamann, Heiko; Wörn, Heinz (Swarm Intelligence)
Designing and analyzing self-organizing systems such as robotic swarms is a challenging task even though we have complete knowledge about the robot’s interior. It is difficult to determine the individual robot’s behavior based on the swarm behavior and vice versa due to the high number of agent–agent interactions. A step towards a solution of this problem is the development of appropriate models which accurately predict the swarm behavior based on a specified control algorithm. Such models would reduce the necessary number of time-consuming simulations and experiments during the design process of an algorithm. In this paper we propose a model with focus on an explicit representation of space because the effectiveness of many swarm robotic scenarios depends on spatial inhomogeneity. We use methods of statistical physics to address spatiality. Starting from a description of a single robot we derive an abstract model of swarm motion. The model is then extended to a generic model framework of communicating robots. In two examples we validate models against simulation results. Our experience shows that qualitative correctness is easily achieved, while quantitative correctness is disproportionately more difficult but still possible.

On Faster Integer Calculations Using Non-arithmetic Primitives - Lürwer-Brüggemeier, Katharina; Ziegler, Martin (Unconventional Computing)

Dynamic Control of Animation Schemes for the Efficient 3D-Visualization of Material Flow Simulations - Laroque, Christoph; Fischer, Matthias; Dangelmaier, Wilhelm; Eikel, Benjamin (Industrial Simulation Conference (ISC 2008))
This paper describes a method for the animation of a large number of objects within a dynamic 3D visualization of a material flow simulation model. It uses key-frame based animation. The number of animated objects may grow constantly in complex simulation models, which might lead to an amount of animations that is too big to be computed in real-time. By the use of a dynamic adjustment, the presented algorithm prefers important animations. Less relevant animations are updated rarely, whereby the selection itself is taken by multiple indicators, e.g. the visible size of the animated object on the screen, in order to keep a good optical impression. Dependent on the computing power of the computer, the algorithm controls the animations in such a way, that the fluid visualization of a large number of objects is still possible. Though the algorithm is to be used within a material flow simulator, it is moreover implemented in a specific animation editor, which allows the design and control of animation schemes. It supports the use of grouping to allow the creation of hierarchical structures for complex animations in a fast and easy manner. The evaluation of the algorithm is proven by a test scene, consisting of tens of thousands animated objects.

Regelung von Animationen in Simulationen von hochdynamischen Fabrikszenen - Laroque, Christoph; Fischer, Matthias; Eikel, Benjamin (Augmented & Virtual Reality in der Produktentstehung)
Dieser Artikel beschreibt eine Methode zur Animation einer großen Anzahl von Objekten zur dynamischen 3D-Visualisierung eines Simulationsmodells mittels der Materialflusssimulation auf Basis von Schlüsselbildern. Die Anzahl zu animierender Objekte ist in komplexen Modellen zu groß, um alle Animationen flüssig darzustellen. Dynamisch abgestuft wählt das entwickelte Verfahren gezielt wichtige Animationen aus, weniger relevante Animationen werden entsprechend seltener animiert. Die Selektion der Animationen erfolgt nach der projizierten Größe der Objekte auf das Ausgabegerät, um einen guten optischen Eindruck beizubehalten. Angepasst an die Leistungsfähigkeit des Rechners wird das Verfahren so geregelt, dass die Visualisierung einer hohen Anzahl von Objekten in Echtzeit möglich bleibt. Das Verfahren ist in einem Editor prototypisch implementiert, mit dem Schlüsselbilder für Objekte erzeugt werden können. Das Gruppieren von Objekten wird erlaubt, so dass eine Hierarchie von Bewegungspfaden definierbar ist. Die Evaluierung der Methode wird mittels Testszenen durchgeführt, die aus mehreren zehntausend animierten Objekten bestehen.

Singular Coverings and Non-Uniform Notions of Closed Set Computability - Le Roux, Stéphane; Ziegler, Martin (Electronic Notes in Theoretical Computer Science)

Who Should Pay for Forwarding Packets? - Ackermann, Heiner; Briest, Patrick; Fanghänel, Alexander; Vöcking, Berthold (Internet Mathematics)
We present a game theoretic study of hybrid communication networks in which mobile devices can connect in an ad hoc fashion to a base station, possibly via a few hops using other mobile devices as intermediate nodes. The maximal number of allowed hops might be bounded with the motivation to guarantee small latency. We introduce hybrid connectivity games to study the impact of selfishness on this kind of infrastructure. Mobile devices are represented by selfish players, each of which aims at establishing an uplink path to the base station minimizing its individual cost. Our model assumes that intermediate nodes on an uplink path are reimbursed for transmitting the packets of other devices. The reimbursements can be paid either by a benevolent network operator or by the senders of the packets using micropayments via a clearing agency that possibly collects a small percentage as commission. These different ways to implement the payments lead to different variants of the hybrid connectivity game. Our main findings are: (1) If there is no constraint on the number of allowed hops on the path to the base station, then the existence of equilibria is guaranteed regardless of whether the network operator or the senders pay for forwarding packets. (2) If the network operator pays, then the existence of equilibria is guaranteed only if at most one intermediate node is allowed, i.e., for at most two hops on the uplink path of a device, but not if the maximal number of allowed hops is three or larger. (3) In contrast, if the senders pay for forwarding their packets, then equilibria are guaranteed to exist given any bound on the number of allowed hops. The equilibrium analysis presented in this paper gives a first game theoretical motivation for the implementation of micropayment schemes in which senders pay for forwarding their packets. We further support this evidence by giving an upper bound on the Price of Anarchy for this kind of hybrid connectivity games that is independent of the number of nodes, but only depends on the number of hops and the power gradient.

Local Strategies for Connecting Stations by Small Robotic Networks - Meyer auf der Heide, Friedhelm; Schneider, Barbara (Biologically-Inspired Collaborative Computing)

Bin Packing oder „Wie bekomme ich die Klamotten in die Kisten?“ - Gehweiler, Joachim; Meyer auf der Heide, Friedhelm (Taschenbuch der Algorithmen)

Planar Visibility Counting - Fischer, Matthias; Hilbig, Matthias; Jähn, Claudius; Meyer auf der Heide, Friedhelm; Ziegler, Martin (arXiv:0810.0052)
For a fixed virtual scene (=collection of simplices) S and given observer position p, how many elements of S are weakly visible (i.e. not fully occluded by others) from p? The present work explores the trade-off between query time and preprocessing space for these quantities in 2D: exactly, in the approximate deterministic, and in the probabilistic sense. We deduce the EXISTENCE of an O(m^2/n^2) space data structure for S that, given p and time O(log n), allows to approximate the ratio of occluded segments up to arbitrary constant absolute error; here m denotes the size of the Visibility Graph--which may be quadratic, but typically is just linear in the size n of the scene S. On the other hand, we present a data structure CONSTRUCTIBLE in O(n*log(n)+m^2*polylog(n)/k) preprocessing time and space with similar approximation properties and query time O(k*polylog n), where k<n is an arbitrary parameter. We describe an implementation of this approach and demonstrate the practical benefit of the parameter k to trade memory for query time in an empirical evaluation on three classes of benchmark scenes.

Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures - SPAA '08

Buying Cheap is Expensive: Hardness of Non-Parametric Multi-Product Pricing - Briest, Patrick; Krysta, Piotr (Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA))

Load Balancing in the Bulk-Synchronous-Parallel Setting using Process Migrations - Bonorden, Olaf (2007 IEEE International Parallel and Distributed Processing Symposium)

Minimal Energy Path Planning for Wireless Robots - Ooi, Chia Ching; Schindelhauer, Christian (ROBOCOMM'07: Proc. of the 1st International Conference on Robot Communication and Coordination)
For the first time, the problem of optimizing energy for communication and motion is investigated. We consider a single mobile robot with continuous high bandwidth wireless communication, e.g. caused by a multimedia application like video surveillance. This robot is connected to a radio base station and moves with constant speed from a given starting point on the plane to a target point. The task is to find the best path such that the energy consumption for mobility and the communication is optimized. This is motivated by the fact that the energy consumption of radio devices increases polynomially (at least to the power of two) with the transmission distance. We introduce efficient approximation algorithms finding the optimal path given the starting point, the target point and the position of the radio stations. We exemplify the influence of the communication cost by a starting scenario with one radio station. We study the performance of the proposed algorithm in simulation, compare it with the scenario without applying our approach, and present the results.

DHHT-RAID: A Distributed Heterogeneous Scalable Architecture for Dynamic Storage Environments - Schomaker, Gunnar (Advanced Information Networking and Applications (AINA-07))

The k-Resource Problem on Uniform and on Uniformly Decomposable Metric Spaces - Bienkowski, Marcin; Kutyłowski, Jarosław (Lecture Notes in Computer Science)
We define a natural generalization of the prominent k-server problem, the k-resource problem. It occurs in metric spaces with some demands and resources given at its points. The demands may vary with time, but the total demand may never exceed k. The goal of an online algorithm is to satisfy demands by moving resources, while minimizing the cost for transporting resources. We give an asymptotically optimal O(log(min {n,k}))-competitive randomized algorithm and an O(min {k,n})-competitive deterministic one for the k-resource problem on uniform metric spaces consisting of n points. This extends known results for paging to the more general setting of k-resource. Basing on the results for uniform metric spaces, we develop a randomized algorithm solving the k-resource and the k-server problem on metric spaces which can be decomposed into components far away from each other. The algorithm achieves a competitive ratio of O(log(min {n,k})), provided that it has some extra resources more than the optimal algorithm.

Peer-to-Peer-Netzwerke - Mahlmann, Peter; Schindelhauer, Christian
Dieses Buch beschäftigt sich mit Algorithmen und Methoden der Peer-to-Peer-Netzwerke und gibt einen Einblick in die aktuelle Forschung. Ursprünglich waren Peer-to-Peer-Netzwerke nur für File-Sharing konzipiert. Mittlerweile hat sich Peer-to-Peer zum Paradigma für Rechnernetzwerke entwickelt. Ziel dieses Buches ist es, dem Leser ein grundlegendes Verständnis der Techniken hinter den aktuellen Peer-to-Peer-Netzwerken aufzuzeigen und im nächsten Schritt Algorithmen vorzustellen, die vielleicht erst in einigen Jahren umgesetzt werden. Das Buch richtet sich in erster Linie an Informatiker (Studenten ab dem 5. Semester). Aber auch interessierte Nichtinformatiker können von diesem Buch profitieren, wobei grundlegende Kenntnisse aus den Bereichen der Mathematik und Informatik vorausgesetzt werden. Die Ziele, Kernaussagen und Ergebnisse sollten jedoch auch ohne akademischen Hintergrund klar werden.

Guarding our digital society's well-being - Leonardi, Stefano; Mahlmann, Peter; Meyer auf der Heide, Friedhelm; Spirakis, Paul G.; Weikum, Gerhard (e-Strategies, www.britishpublishers.com)

Why Robots Need Maps - Dynia, Miroslaw; Łopuszański, Jakub; Schindelhauer, Christian (Proc. of the 14th Colloquium on Structural Information and Communication Complexity (SIROCCO))

Competitive Maintenance of Minimum Spanning Trees in Dynamic Graphs - Dynia, Miroslaw; Korzeniowski, Miroslaw; Kutyłowski, Jarosław (Proc. of the 33rd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM'07))

Using Mobile Relays for Ensuring Connectivity in Sparse Networks - Kutylowski, Jaroslaw

Competitive Maintenance of Minimum Spanning Trees under Stochastic Adversaries - Kutylowski, Jaroslaw

Orientation in a Trail Network by Exploiting its Geometry for Swarm Robotics - Dorigo, Marco; Hamann, Heiko; Szymanski, Marc; Wörn, Heinz; Shi, Yuhui (IEEE Swarm Intelligence Symposium, Honolulu, USA, April 1-5)

An analytical and spatial model of foraging in a swarm of robots - Hamann, Heiko; Wörn, Heinz; Sahin, Erol; Spears, Winfield; Winfield, Winfield (Swarm Robotics - Second SAB 2006 International Workshop)

A Space- and Time-Continuous Model of Self-Organizing Robot Swarms for Design Support - Hamann, Heiko; Wörn, Heinz (First International Conference on Self-Adaptive and Self-Organizing Systems (SASO 2007))
Designing and implementing artificial self-organizing systems is a challenging task since they typically behave non- intuitive and only little theoretical foundations exist. Predicting a system of many components with a huge amount of interactions is beyond human skills. The currently common use of simulations for design support is not satisfying, as it is time-consuming and the results are most likely sub- optimal. In this work, we present the derivation of an analytical, time-, and space-continuous model for a swarm of autonomous robots based on the Fokker-Planck equation. While the motion model is in most parts physically motivated, the communication model is based on a heuristic approach. A showcase application to a recently proposed scenario of collective perception in a huge swarm of robots with very limited abilities is given and the simulation results are compared to the model. Despite the high level of abstraction, the prediction discrepancies are small and the parameters can be mapped one-to-one from the model to the control algorithm. Finally, we give an outlook on the capabilities of the proposed model, discuss its limitations, and suggest an improvement that could reduce the number of empirically determined parameters.

Embodied Computation - Hamann, Heiko; Wörn, Heinz; Nagy, Marius; Nagy, Naya (Parallel Processing Letters)

From Micro to Nano and Swarm Robotics - Hamann, Heiko; Szymanski, Marc; Wörn, Heinz; Estana, Ramon; Xie, Ming; Dubowsky, Steven (Advances in Climbing and walking robots. Proceedings of 10th International Conference (CLAWAR'07), Singapore, July 16-18)
Current research in Micro, Nano and Swarm Robots as results of the European projects Miniman, MiCRoN and I-SWARM will be presented. First, the design and the control of 5 to 10cm3 sized mobile micro robots with five degrees of freedom will be shown. They can handle miniaturized parts as for example an optical component or a biological cell with a size in the micrometre-area with an accuracy of 100nm under a microscope or a raster-electron microscope. Second, the design and the control of a 1cm3-sized mobile untethered micro robot will be demonstrated. Here, the robot consists of five parts: the Piezzo locomotion module, the micro control unit, the communication unit, the navigation system and the micro gripper. The mobile robot can be guided and positioned in an arena with an accuracy of 5 micrometre and can be programmed and controlled over the wireless communication unit. Third, the design and the control of 3 × 3 × 3 mm3 sized micro-/nanorobots with 2 degrees of freedom will be presented. The transmission of energy and the communication between the robots is realized via infrared. The robot controller is fully integrated and has limited functionalities. Via basic sensors communication functions and elementary rules and behaviours the micro robot can act in a swarm consisting of hundreds and thousands of robots. Future applications could be monitoring-, inspection-, exploring-tasks etc. of big areas or objects.

Revising Type-2 Computation and Degrees of Discontinuity - Ziegler, Martin (Electronic Notes in Theoretical Computer Science)

Real Hypercomputation and Continuity - Ziegler, Martin (Theory of Computing Systems)

(Short) Survey of Real Hypercomputation - Ziegler, Martin (Lecture Notes in Computer Science)

Real Computational Universality: The Word Problem for a Class of Groups with Infinite Presentation - Meer, Klaus; Ziegler, Martin (Mathematical Foundations of Computer Science 2007)

On Faster Integer Calculations using Non-Arithmetic Primitives - Lürwer-Brüggemeier, Katharina; Ziegler, Martin (arXiv:0709.0624)
The unit cost model is both convenient and largely realistic for describing integer decision algorithms over (+,*). Additional operations like division with remainder or bitwise conjunction, although equally supported by computing hardware, may lead to a considerable drop in complexity. We show a variety of concrete problems to benefit from such NON-arithmetic primitives by presenting and analyzing corresponding fast algorithms.

Real Computability and Hypercomputation - Ziegler, Martin

Interactive Refinement of a Material Flow Simulation Model by Comparing Multiple Simulation Runs in one 3D Environment - Fischer, Matthias; Laroque, Christoph; Huber, Daniel; Krokowski, Jens; Mueck, Bengt; Kortenjan, Michael; Aufenanger, Mark; Dangelmaier, Wilhelm (European Simulation and Modelling Conference (ESM 2007))
The validation of material flow models as well as the selection of promising strategies for the generation of a successful experiment plan is a time-consuming process. A new approach is presented, which supports the simulation expert in his working process by giving him the opportunity to modify the simulated simulation run and afterwards compare the effects of his modification with the original setting, online and in one user interface, implemented by switching the visualizations between the simulation runs or opening up to 5 parallel 3D windows. The method developed therefore clones existing simulation runs online and allows the navigation within these existing simulation runs. The method has been implemented and is validated by a test model, which describes in detail the new working process of a modeler. New research questions are derived from this work, which will define following working steps.

Ein ganzheitlicher Ansatz zur immersiven 3D-Materialflusssimulation innerhalb der Digitalen Fabrik - Dangelmaier, Wilhelm; Laroque, Christoph; Fischer, Matthias (Augmented & Virtual Reality in der Produktentstehung)

Estimating Clustering Indexes in Data Streams - Buriol, Luciana S.; Frahling, Gereon; Leonardi, Stefano; Sohler, Christian (Proceedings of the 15th European Symposium on Algorithms (ESA))
We present random sampling algorithms that with probability at least 1 − δ compute a (1 ±ε)-approximation of the clustering coefficient and of the number of bipartite clique subgraphs of a graph given as an incidence stream of edges. The space used by our algorithm to estimate the clustering coefficient is inversely related to the clustering coefficient of the network itself. The space used by our algorithm to compute the number K 3,3 of bipartite cliques is proportional to the ratio between the number of K 1,3 and K 3,3 in the graph. Since the space complexity depends only on the structure of the input graph and not on the number of nodes, our algorithms scale very well with increasing graph size. Therefore they provide a basic tool to analyze the structure of dense clusters in large graphs and have many applications in the discovery of web communities, the analysis of the structure of large social networks and the probing of frequent patterns in large graphs. We implemented both algorithms and evaluated their performance on networks from different application domains and of different size; The largest instance is a webgraph consisting of more than 135 million nodes and 1 billion edges. Both algorithms compute accurate results in reasonable time on the tested instances.

On Testable Properties in Bounded Degree Graphs - Sohler, Christian; Czumaj, Artur (Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA'07))
We study graph properties which are testable for bounded degree graphs in time independent of the input size. Our goal is to distinguish between graphs having a predetermined graph property and graphs that are far from every graph having that property. It is believed that almost all, even very simple graph properties require a large complexity to be tested for arbitrary (bounded degree) graphs. Therefore in this paper we focus our attention on testing graph properties for special classes of graphs. We call a graph family non-expanding if every graph in this family is not a weak expander (its expansion is O(1/log2 n), where n is the graph size). A graph family is hereditary if it is closed under vertex removal. Similarly, a graph property is hereditary if it is closed under vertex removal. Next, we call a graph property Π to be testable for a graph family F if for every graph G ε F, in time independent of the size of G we can distinguish between the case when G satisfies property Π and when it is far from every graph satisfying property Π. In this paper we prove thatIn the bounded degree graph model, any hereditary property is testable if the input graph belongs to a hereditary and non-expanding family of graphs.As an application, our result implies that, for example, any hereditary property (e.g., k-colorability, H-freeness, etc.) is testable in the bounded degree graph model for planar graphs, graphs with bounded genus, interval graphs, etc. No such results have been known before and prior to our work, in the bounded degree graph model very few graph properties have been known to be testable for any graph classes.

StrSort Algorithms for Geometric Problems - Sohler, Christian; Lammersen, Christiane (Proceedings of the 23rd European Workshop on Computational Geometry (EWCG))
In the StrSort model [2], the input is given as a stream, e.g. a sequence of points, and an algorithm can perform (a) streaming and (b) sorting passes to process the stream. A streaming pass reads the input stream from left to right and writes an output stream, which is the input of the next pass. A sorting pass is a black box operation that sorts a stream according to some partial order. In this paper, we develop algorithms for two basic geometric problems in the StrSort model. At first, we propose a divide-and-conquer algorithm that computes the convex hull of a point set in 2D in O(log2 n) passes using O(1) memory. Then we give a StrSort algorithm to compute a (1+ε)-spanner for a point set in Rd for constant d and constant epsilon that uses O(logd-1 n) passes and O(log n) space. This result implies a (1+ε)-approximation of the Euclidean minimum spanning tree in Rd, for constant d and ε.

Testing Expansion in Bounded-Degree Graphs - Sohler, Christian; Czumaj, Artur (Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS))

Small Space Representations for Metric Min-Sum k-Clustering and their Applications - Sohler, Christian; Czumaj, Artur (Proceedings of the 24th International Symposium on Theoretical Aspects of Computer Science (STACS'07))

Sublinear-time approximation algorithms for clustering via random sampling - Sohler, Christian; Czumaj, Artur (Random Structures & Algorithms)
We present a novel analysis of a random sampling approach for four clustering problems in metric spaces: k-median, k-means, min-sum k-clustering, and balanced k-median. For all these problems, we consider the following simple sampling scheme: select a small sample set of input points uniformly at random and then run some approximation algorithm on this sample set to compute an approximation of the best possible clustering of this set. Our main technical contribution is a significantly strengthened analysis of the approximation guarantee by this scheme for the clustering problems.The main motivation behind our analyses was to design sublinear-time algorithms for clustering problems. Our second contribution is the development of new approximation algorithms for the aforementioned clustering problems. Using our random sampling approach, we obtain for these problems the first time approximation algorithms that have running time independent of the input size, and depending on k and the diameter of the metric space only. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007A preliminary extended abstract of this work appeared in Proceedings of the 31st Annual International Colloquium on Automata, Languages and Programming (ICALP), pp. 396407, 2004.

A PTAS for k-means clustering based on weak coresets - Sohler, Christian; Monemizahdeh, Morteza; Feldman, Dan (Proceedings of the 23rd annual symposium on computational geometry (SoCG'07))

Efficient kinetic data structures for MaxCut - Sohler, Christian; Czumaj, Artur; Frahling, Gereon (Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG))

Dynamic and redundant data placement - Brinkmann, André; Effert, Sascha; Meyer auf der Heide, Friedhelm; Scheideler, Christian (IEEE International Conference on Distributed Computing Systems (ICDCS))
We present a randomized block-level storage virtualization for arbitrary heterogeneous storage systems that can distribute data in a fair and redundant way and can adapt this distribution in an efficient way as storage devices enter or leave the system. More precisely, our virtualization strategies can distribute a set of data blocks among a set of storage devices of arbitrary non-uniform capacities so that a storage device representing x% of the capacity in the system will get x% of the data (as long as this is in principle possible) and the different copies of each data block are stored so that no two copies of a data block are located in the same device. Achieving these two properties is not easy, and no virtualization strategy has been presented so far that has been formally shown to satisfy fairness and redundancy while being time- and space-eflcient and allowing an efficient adaptation to a changing set of devices.

Smart Teams: Simulating Large Robotic Swarms in Vast Environments - Arens, Stephan; Buss, Alexander; Deck, Helena; Dynia, Miroslaw; Fischer, Matthias; Hagedorn, Holger; Isaak, Peter; Kutylowski, Jaroslaw; Meyer auf der Heide, Friedhelm; Nesterow, Viktor; Ogiermann, Adrian; Stobbe, Boris; et al. (Proceedings of the 4th International Symposium on Autonomous Minirobots for Research and Edutainment)
We consider the problem of exploring an unknown environment using a swarm of autonomous robots with collective behavior emerging from their local rules. Each robot has only a very restricted view on the environment which makes cooperation difficult. We introduce a software system which is capable of simulating a large number of such robots (e.g. 1000) on highly complex terrains with millions of obstacles. Its main purpose is to easily integrate and evaluate any kind of algorithm for controlling the robot behavior. The simulation may be observed in real-time via a visualization that displays both the individual and the collective progress of the robots. We present the system design, its main features and underlying concepts.

Local strategies for maintaining a chain of relay stations between an explorer and a base station - Dynia, Miroslaw; Kutylowski, Jaroslaw; Meyer auf der Heide, Friedhelm; Schrieb, Jonas (Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures - SPAA '07)

Efficient Collision Detection for Point and Polygon Based Models - Klein, Jan

Position-based Routing Strategies - Rührup, Stefan

Single-Minded Unlimited Supply Pricing on Sparse Instances - Briest, Patrick; Krysta, Piotr (Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA))

Energy-Efficient Broadcast Scheduling for Speed-Controlled Transmission Channels - Briest, Patrick; Gunia, Christian (Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC))

Die Analyse von Estimation-of-Distribution-Algorithmen auf ausgewählten Funktionen - Degener, Bastian

Distributed random digraph transformations for peer-to-peer networks - Mahlmann, Peter; Schindelhauer, Christian (Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures - SPAA '06)
We study the problem of designing an adaptive hash table for redundant data storage in a system of storage devices with arbitrary capacities. Ideally, such a hash table should make sure that (a) a storage device with x% of the available capacity should get x% of the data, (b) the copies of each data item are distributed among the storage devices so that no two copies are stored at the same device, and (c) only a near-minimum amount of data replacements is necessary to preserve (a) and (b) under any change in the system. Hash tables satisfying (a) and (c) are already known, and it is not difficult to construct hash tables satisfying (a) and (b). However, no hash table is known so far that can satisfy all three properties as long as this is in principle possible. We present a strategy called SPREAD that solves this problem for the first time. As long as (a) and (b) can in principle be satisfied, SPREAD preserves (a) for every storage device nearly optimal, with high probability, guarantees (b) for every data item, and only needs a constant factor more data replacements than minimum possible in order to preserve (a) and (b).

Online Multi-path Routing in a Maze - Rührup, Stefan; Schindelhauer, Christian (Proc. of the 17th International Symposium on Algorithms and Computation (ISAAC 2006))

SAN Optimal Multi Parameter Access Scheme - Schindelhauer, Christian; Schomaker, Gunnar (5th International Conference on Networking (ICN))
Storage Area Networks commonly consist a more or less static set of n data servers that handle a dynamic collection of m documents. Such SANs can minimize the access time to documents by distributing each document among several servers, allowing users to access documents in parallel. This paper describes an efficient solution for providing parallel access to multiple hard disks for popular content. In extension to previous approaches we provide an efficient and elegant hash table data structure for utilizing the full capacity of each data server. Concerning the dynamics, documents as well as server may be added or removed from the system causing only local changes. We consider sequential and parallel access to data in the average case. For the average time model we present a fast optimal algorithm.

Improved Bounds for Online Multi-Path Routing in Faulty Mesh Networks - Rührup, Stefan; Schindelhauer, Christian

Predictive Replication and Placement Strategies for Movie Documents in heterogeneous Content Delivery Networks - Schomaker, Gunnar; Loeser, Christoph; Schubert, Matthias (5th International Conference on Networking (ICN).)
In previous publications there have been several proposals regarding replica generation and placement of movie content in content-distribution-networks or P2P overlays. Within this paper we extend approaches for heterogeneous placement scenarios described in prior publications. Therefor we presume heterogeneous server peers' bandwidth, HD capacity, and movie popularities. Movie documents are replicated and placed onto server peers with respect to the predicted popularity values. Thus each document aims to gain fair networks resources according to its popularity. We present simulation results of heuristics of different placement strategies and compare them with a near optimal technique.

Realizing Multilevel Snapshots in Dynamically Changing Virtualized Storage Environments - Brinkmann, Andre; Effert, Sascha; Heidebuer, Michael; Vodisek, Mario (5th International Conference on Networking (ICN))

Size equivalent cluster trees (SEC-Trees) realtime rendering of large industrial scenes - Kortenjan, Michael; Schomaker, Gunnar (4th International Conference on Virtual Reality, Computer Graphics, Visualization and Interaction (Afrigraph 2006))
#hniid 2484

Reliable Broadcasting Without Collision Detection - Kutyłowski, Jarosław; Zagórski, Filip (SOFSEM 2006: Theory and Practice of Computer Science)
We propose a dynamic, ad-hoc communication network consisting of mobile units that can warn about traffic jams on motorways. Our goal is to provide a practical, low cost solution. Therefore we consider very simple wireless communication hardware, without collision detection, with very small bandwidth and a probabilistic model of link failure. We provide a complete system architecture. For this purpose we design and analyze solutions for size approximation, leader election and broadcasting. Our algorithms are fine-tuned for fast operation in a practical setting. We provide both a theoretical and experimental evaluation of our solutions. Our contribution is much different from the previous work, where either pure theoretical models with a pure theoretical analysis are provided or algorithms working in practical models are evaluated only through simulations.

Influence of adaptive data layouts on performance in dynamically changing storage environments - Brinkmann, Andre; Effert, Sascha; Heidebuer, Michael; Vodisek, Mario (14th Euromicro International Conference on Parallel, Distributed, and Network-Based Processing (PDP'06))
For most of today's IT environments, the tremendous need for storage capacity in combination with a required minimum I/O performance has become highly critical. In dynamically growing environments, a storage management solution's underlying data distribution scheme has great impact to the overall system I/O performance. The evaluation of a number of open system storage visualization solutions and volume managers has shown that all of them lack the ability to automatically adapt to changing access patterns and storage infrastructures; many of them require an error prone manual re-layout of the data blocks, or rely on a very time consuming re-striping of all available data. This paper evaluates the performance of conventional data distribution approaches compared to the adaptive virtualization solution V:DRIVE in dynamically changing storage environments. Changes of the storage infrastructure are normally not considered in benchmark results, but can have a significant impact on storage performance. Using synthetic benchmarks, V:DRIVE is compared in such changing environments with the non-adaptive Linux logical volume manager (LVM). The performance results of our tests clearly outline the necessity of adaptive data distribution schemes.

Self-Coordinating Systems: The Next Challenge in Research on Distributed Systems
We present a parallel algorithm for the rendering of complex three-dimensional scenes. The algorithm runs across heterogeneous architectures of PC-clusters consisting of a visualization-node, equipped with a powerful graphics adapter, and cluster nodes requiring weaker graphics capabilities only. The visualization-node renders a mixture of scene objects and simplified meshes (Reliefboards). The cluster nodes assist the visualization-node by asynchronous computing of Reliefboards, which are used to replace and render distant parts of the scene. Our algorithm is capable of gaining significant speedups if the cluster's nodes provide weak graphics adapters only. We trade the number of cluster nodes off the scene objects' image quality.

New trends in parallel and distributed computing - Monien, Burkhard; Meyer auf der Heide, Friedhelm

Directional Communication in Mobile Ad Hoc Networks - Grünewald, Matthias; Meyer auf der Heide, Friedhelm; Rührup, Stefan; Schindelhauer, Christian; Volbert, Klaus (New Trends in Parallel & Distributed Computing, 6th Int. Heinz Nixdorf Symposium)

Computing Clustering Coefficients in Data Streams - Sohler, Christian; Frahling, Gereon; Marchetti-Spaccamela, Alberto; Leonardi, Stefano; Buriol, Luciana (Proceedings of the European Conference on Complex Systems (ECCS'06))
We present random sampling algorithms that with probability at least 1 - δ compute a (1 ± ǫ)- approximation of the clustering coefficient, the transitiv ity coefficient, and of the number of bipartite cliques in a graph given as a stream of edges. Our methods can be extended to approximately count the number of occurences of fixed constant-size subgraphs. Our a lgorithms only require one pass over the input stream and their storage space depends only on structural parameters of the graphs, the approxi- mation guarantee, and the confidence probability. For examp le, the algorithms to compute the clustering and transitivity coefficient depend on that coefficient but n ot on the size of the graph. Since many large social networks have small clustering and transitivity coe fficient, our algorithms use space independent of the size of the input for these graphs. We implemented our algorithms and evaluated their performance on networks from different appli- cation domains. The sizes of the considered input graphs varied from about 8, 000 nodes and 40, 000 edges to about 135 million nodes and more than 1 billion edges. For both algorithms we run experiments with a sample set size varying from 100, 000 to 1, 000, 000 to evaluate running time and approximation guarantee. Our algorithms appear to be time efficient for the se sample sizes.

Counting Triangles in Data Streams - Sohler, Christian; Frahling, Gereon; Marchetti-Spaccamela, Alberto; Leonardi, Stefano; Buriol, Luciana

A Distributed O(1)-Approximation Algorithm for the Uniform Facility Location Problem - Sohler, Christian; Gehweiler, Joachim; Lammersen, Christiane (Proceeedings of 18th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA))
In this paper, we present a randomized constant factor approximation algorithm for the metric minimum facility location problem with uniform costs and demands in a distributed setting, in which every point can open a facility. In particular, our distributed algorithm uses three communication rounds with message sizes bounded to O(log n) bits where n is the number of points. We also extend our algorithm to constant powers of metric spaces, where we also obtain a randomized constant factor approximation algorithm.

Power-Aware Collective Tree Exploration - Dynia, Miroslaw; Korzeniowski, Miroslaw; Schindelhauer, Christian (Architecture of Computing Systems - ARCS)