TY - CONF AB - 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+\epsilon} n) communication rounds and yields a \my^4(1+4\my^2(1+\epsilon)^{1/p})^p approximation, while the second has a running time of expected O(log^2_{1+\epsilon} n) communication rounds and an approximation factor of \my^4(1 + 2(1 + \epsilon)^{1/p})^p. Here, \epsilon > 0 is an arbitrarily small constant, p the exponent of the polynomial representing the communication costs, and \my the relative measurement error. AU - Abshoff, Sebastan AU - Cord-Landwehr, Andreas AU - Degener, Bastian AU - Kempkes, Barbara AU - Pietrzyk, Peter ID - 657 T2 - Proceedings of the 7th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities (ALGOSENSORS) TI - Local Approximation Algorithms for the Uncapacitated Metric Facility Location Problem in Power-Aware Sensor Networks ER - TY - GEN AU - Swierkot, Kamil ID - 663 TI - Complexity Classes for Local Computation ER - TY - CONF AB - 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. AU - Gehweiler, Joachim AU - Kling, Peter AU - Meyer auf der Heide, Friedhelm ID - 664 T2 - Proceedings of the 9th International Conference on Parallel Processing and Applied Mathematics (PPAM) TI - An Experimental Comparison of Load Balancing Strategies in a Web Computing Environment ER - TY - GEN ED - Meyer auf der Heide, Friedhelm ED - Rajaraman, Rajmohan ID - 667 TI - 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures ER - TY - CONF AB - 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. AU - Cord-Landwehr, Andreas AU - Degener, Bastian AU - Fischer, Matthias AU - Hüllmann, Martina AU - Kempkes, Barbara AU - Klaas, Alexander AU - Kling, Peter AU - Kurras, Sven AU - Märtens, Marcus AU - Meyer auf der Heide, Friedhelm AU - Raupach, Christoph AU - Swierkot, Kamil AU - Warner, Daniel AU - Weddemann, Christoph AU - Wonisch, Daniel ID - 16410 IS - 6543 SN - 0302-9743 T2 - 37th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2011) TI - Collisionless Gathering of Robots with an Extent ER - TY - CHAP AU - Gehweiler, Joachim AU - Meyer auf der Heide, Friedhelm ID - 16412 SN - 9783642153273 T2 - Algorithms Unplugged TI - Bin Packing - How Do I Get My Stuff into the Boxes ER - TY - CONF AU - Rajaraman, Rajmohan AU - Meyer auf der Heide, Friedhelm ID - 16428 SN - 9781450307437 TI - Proceedings of the 23rd ACM symposium on Parallelism in algorithms and architectures - SPAA '11 ER - TY - JOUR AU - Degener, Bastian AU - Fekete, Sándor P. AU - Kempkes, Barbara AU - Meyer auf der Heide, Friedhelm ID - 16447 JF - Computer Science Review SN - 1574-0137 TI - A survey on relay placement with runtime and approximation guarantees ER - TY - CONF AU - Brandes, Philipp AU - Degener, Bastian AU - Kempkes, Barbara AU - Meyer auf der Heide, Friedhelm ID - 16451 T2 - SIROCCO '11: Proc. of the 18th International Colloquium on Structural Information and Communication Complexity TI - Energy-efficient strategies for building short chains of mobile robots locally ER - TY - CONF AU - Degener, Bastian AU - Kempkes, Barbara AU - Langner, Tobias AU - Meyer auf der Heide, Friedhelm AU - Pietrzyk, Peter AU - Wattenhofer, Roger ID - 16453 SN - 9781450307437 T2 - Proceedings of the 23rd ACM symposium on Parallelism in algorithms and architectures - SPAA '11 TI - A tight runtime bound for synchronous gathering of autonomous robots with limited visibility ER - TY - CONF AU - Kling, Peter AU - Meyer auf der Heide, Friedhelm ID - 16454 SN - 9781450307437 T2 - Proceedings of the 23rd ACM symposium on Parallelism in algorithms and architectures - SPAA '11 TI - Convergence of local communication chain strategies via linear transformations ER - TY - JOUR AU - Degener, Bastian AU - Kempkes, Barbara AU - Meyer auf der Heide, Friedhelm ID - 16455 JF - Procedia Computer Science SN - 1877-0509 TI - Building Simple Formations in Large Societies of Tiny Mobile Robots ER - TY - CHAP AU - Degener, Bastian AU - Kempkes, Barbara AU - Meyer auf der Heide, Friedhelm ID - 16456 SN - 9783034801294 T2 - Organic Computing — A Paradigm Shift for Complex Systems TI - Energy-Awareness in Self-organising Robotic Exploration Teams ER - TY - CHAP AU - Brandes, Philipp AU - Degener, Bastian AU - Kempkes, Barbara AU - Meyer auf der Heide, Friedhelm ID - 16459 SN - 0302-9743 T2 - Structural Information and Communication Complexity TI - Energy-Efficient Strategies for Building Short Chains of Mobile Robots Locally ER - TY - JOUR AU - Hsu, D. Frank AU - Magga, Bruce M. AU - Ho, Howard C. T. AU - Hromkovic, Juraj AU - Lau, Francis C. M. AU - Meyer auf der Heide, Friedhelm ID - 17009 JF - Journal of Interconnection Networks SN - 0219-2659 TI - EDITORIAL ER - TY - CHAP AB - Given a set of n mobile robots in the d-dimensional Euclidean space, the goal is to let them converge to a single not predefined point. The challenge is that the robots are limited in their capabilities. Robots can, upon activation, compute the positions of all other robots using an individual affine coordinate system. The robots are indistinguishable, oblivious and may have different affine coordinate systems. A very general discrete time model assumes that robots are activated in arbitrary order. Further, the computation of a new target point may happen much earlier than the movement, so that the movement is based on outdated information about other robot's positions. Time is measured as the number of rounds, where a round ends as soon as each robot has moved at least once. In [Cohen, Peleg: Convergence properties of gravitational algorithms in asynchronous robot systems], the Center of Gravity is considered as target function, convergence was proven, and the number of rounds needed for halving the diameter of the convex hull of the robot's positions was shown to be O(n^2) and Omega(n). We present an easy-to-check property of target functions that guarantee convergence and yields upper time bounds. This property intuitively says that when a robot computes a new target point, this point is significantly within the current axes aligned minimal box containing all robots. This property holds, e.g., for the above-mentioned target function, and improves the above O(n^2) to an asymptotically optimal O(n) upper bound. Our technique also yields a constant time bound for a target function that requires all robots having identical coordinate axes. AU - Cord-Landwehr, Andreas AU - Degener, Bastian AU - Fischer, Matthias AU - Hüllmann, Martina AU - Kempkes, Barbara AU - Klaas, Alexander AU - Kling, Peter AU - Kurras, Sven AU - Märtens, Marcus AU - Meyer auf der Heide, Friedhelm AU - Raupach, Christoph AU - Swierkot, Kamil AU - Warner, Daniel AU - Weddemann, Christoph AU - Wonisch, Daniel ID - 16409 SN - 0302-9743 T2 - Automata, Languages and Programming TI - A New Approach for Analyzing Convergence Algorithms for Mobile Robots ER - TY - CONF AU - Briest, Patrick AU - Röglin, Heiko ID - 19678 T2 - Workshop on Approximation and Online Algorithms (WAOA) TI - The Power of Uncertainty: Bundle-Pricing for Unit-Demand Customers VL - 6534 ER - TY - CONF AU - Degener, Bastian AU - Pietrzyk, Peter AU - Kempkes, Barbara ID - 19711 T2 - International Parallel & Distributed Processing Symposium (IPDPS) TI - A local, distributed constant-factor approximation algorithm for the dynamic facility location problem ER - TY - CONF AB - We introduce the Read-Write-Coding-System (RWC) – a very flexible class of linear block codes that generate efficient and flexible erasure codes for storage networks. In particular, given a message x of k symbols and a codeword y of n symbols, an RW code defines additional parameters k \leq r,w \leq n that offer enhanced possibilities to adjust the fault-tolerance capability of the code. More precisely, an RWC provides linear $\left(n,k,d\right)$-codes that have (a) minimum distance d=n-r+1 for any two codewords, and (b) for each codeword there exists a codeword for each other message with distance of at most w. Furthermore, depending on the values r,w and the code alphabet, different block codes such as parity codes (e.g. RAID 4/5) or Reed-Solomon (RS) codes (if r=k and thus, w=n) can be generated. In storage networks in which I/O accesses are very costly and redundancy is crucial, this flexibility has considerable advantages as r and w can optimally be adapted to read or write intensive applications; only w symbols must be updated if the message x changes completely, what is different from other codes which always need to rewrite y completely as x changes. In this paper, we first state a tight lower bound and basic conditions for all RW codes. Furthermore, we introduce special RW codes in which all mentioned parameters are adjustable even online, that is, those RW codes are adaptive to changing demands. At last, we point out some useful properties regarding safety and security of the stored data. AU - Mense, Mario AU - Schindelhauer, Christian ID - 19796 SN - 0302-9743 T2 - Proceedings of 11th International Symposium on Stabilization, Safety, and Security of Distributed Systems TI - Read-Write-Codes: An Erasure Resilient Encoding System for Flexible Reading and Writing in Storage Networks VL - 5873 ER - TY - CONF AB - We present 3nuts, a self-stabilizing peer-to-peer (p2p) network supporting range queries and adapting the overlay structure to the underlying physical network. 3nuts combines concepts of structured and unstructured p2p networks to overcome their individual shortcomings while keeping their strengths. This is achieved by combining self maintaining random networks for robustness, a search tree to allow range queries, and DHTs for load balancing. Simple handshake operations with provable guarantees are used for maintenance and self-stabilization. Efficiency of load balancing, fast data access, and robustness are proven by rigorous analysis. AU - Janson, Thomas AU - Mahlmann, Peter AU - Schindelhauer, Christian ID - 19824 SN - 9781424497270 T2 - Proceedings of the 16th International Conference on Parallel and Distributed Systems TI - A Self-Stabilizing Locality-Aware Peer-to-Peer Network Combining Random Networks, Search Trees, and DHTs ER - TY - CONF AU - Miao, Huawei AU - Ooi, Chia Ching AU - Wu, Xiaowen AU - Schindelhauer, Christian ID - 19829 SN - 9781605586397 T2 - Proceedings of the 2010 ACM Symposium on Applied Computing - SAC '10 TI - Coverage-hole trap model in target tracking using distributed relay-robot network ER - TY - CONF AU - Schomaker, Gunnar AU - Oberthur, Simon AU - Kortenjan, Michael ID - 19933 SN - 9781424472987 T2 - 8th IEEE International Conference on Industrial Informatics (INDIN'2010) TI - Distributed and dynamic resource management for self-optimizing mechatronic systems ER - TY - BOOK AU - Hamann, Heiko ID - 20182 TI - Space-Time Continuous Models of Swarm Robotics Systems: Supporting Global-to-Local Programming ER - TY - CONF AU - Hamann, Heiko AU - Schmickl, Thomas AU - Stradner, Jürgen AU - Crailsheim, Karl ID - 20220 T2 - Proceedings of the IEEE Congress on Evolutionary Computation (CEC'10) TI - A Hormone-Based Controller for Evolutionary Multi-Modular Robotics: From Single Modules to Gait Learning ER - TY - CONF AU - Schmickl, Thomas AU - Hamann, Heiko AU - Stradner, Jürgen AU - Mayet, Ralf AU - Crailsheim, Karl ID - 20222 T2 - Proc. of the ALife XII Conference TI - Complex Taxis-Behaviour in a Novel Bio-Inspired Robot Controller ER - TY - CONF AB - The semi-automatic or automatic synthesis of robot controller software is both desirable and challenging. Synthesis of rather simple behaviors such as collision avoidance by applying artificial evolution has been shown multiple times. However, the difficulty of this synthesis increases heavily with increasing complexity of the task that should be performed by the robot. We try to tackle this problem of complexity with Artificial Homeostatic Hormone Systems (AHHS), which provide both intrinsic, homeostatic processes and (transient) intrinsic, variant behavior. By using AHHS the need for pre-defined controller topologies or information about the field of application is minimized. We investigate how the principle design of the controller and the hormone network size affects the overall performance of the artificial evolution (i.e., evolvability). This is done by comparing two variants of AHHS that show different effects when mutated. We evolve a controller for a robot built from five autonomous, cooperating modules. The desired behavior is a form of gait resulting in fast locomotion by using the modules' main hinges. AU - Hamann, Heiko AU - Stradner, Jürgen AU - Schmickl, Thomas AU - Crailsheim, Karl ID - 20223 T2 - Artificial Life XII (ALife XII), Odense, Denmark TI - Artificial Hormone Reaction Networks: Towards Higher Evolvability in Evolutionary Multi-Modular Robotics ER - TY - CONF AU - Hamann, Heiko AU - Meyer, Bernd AU - Schmickl, Thomas AU - Crailsheim, Karl ID - 20226 SN - 0302-9743 T2 - From Animals to Animats 11 TI - A Model of Symmetry Breaking in Collective Decision-Making VL - 6226 ER - TY - CONF AB - Self-organization in natural systems demonstrates very reliable and scalable collective behavior without using any central elements. When providing collective robotic systems with self-organizing principles, we are facing new problems of making self-organization purposeful, self-adapting to changing environments and faster, in order to meet requirements from a technical perspective. This paper describes on-going work of creating such an artificial self-organization within artificial robot organisms, performed in the framework of several European projects. AU - Kernbach, Serge AU - Hamann, Heiko AU - Stradner, Jürgen AU - Thenius, Ronald AU - Schmickl, Thomas AU - Crailsheim, Karl AU - Rossum, A.C. van AU - Sebag, Michele AU - Bredeche, Nicolas AU - Yao, Yao AU - Baele, Guy AU - Peer, Yves Van de AU - Timmis, Jon AU - Mohktar, Maizura AU - Tyrrell, Andy AU - Eiben, A.E. AU - McKibbin, S.P. AU - Liu, Wenguo AU - Winfield, Alan F.T. ID - 20258 SN - 9781424451661 T2 - 2009 Computation World: Future Computing, Service Computation, Cognitive, Adaptive, Content, Patterns TI - On Adaptive Self-Organization in Artificial Robot Organisms ER - TY - JOUR AU - Grza̧ślewicz, Ryszard AU - Kutyłowski, Jarosław AU - Kutyłowski, Mirosław AU - Pietkiewicz, Wojciech ID - 24282 JF - ICCSA'05: Proceedings of the 2005 international conference on Computational Science and Its Applications SN - 0302-9743 TI - Robust Undetectable Interference Watermarks ER - TY - CONF AU - Samara, Sufyan AU - Schomaker, Gunnar ID - 27159 T2 - 2010 10th IEEE International Conference on Computer and Information Technology TI - Real-time Adaptation and Load Balancing Aware OS Services for Distributed Reconfigurable System on Chip ER - TY - CONF AB - Commercial software of material flow simulations has the ability to layout the simulated models. Arranged equipment, such as conveyors or machines, includes the need to model and determine motion paths for moving objects like forklifts or automatically guided vehicles, so that the simulation framework is able to navigate all vehicles across those motion paths. After analyzing first scenarios, the user often carries out layout changes in the simulation model, e.g. moving, adding or deleting equipment. However, those changes cause time consuming, additional modeling of the motion paths for the user. Our motion planning algorithm reduces these changes by automatically determining the motion paths for moving objects, depending on an actual model layout without colliding with other objects. The algorithm works on the basis of the virtual scene’s 3D-data used for the simulation model’s visualization. We demonstrate the technique with a multi-floor building example. AU - Fischer, Matthias AU - Renken, Hendrik AU - Laroque, Christoph AU - Schaumann, Guido AU - Dangelmaier, Wilhelm ID - 17422 SN - 9781424498666 T2 - Proceedings of the 2010 Winter Simulation Conference TI - Automated 3D-motion planning for ramps and stairs in intra-logistics material flow simulations ER - TY - GEN AU - Gehweiler, Joachim AU - Meyer auf der Heide, Friedhelm AU - Schroeder, Ulf-Peter ID - 17462 TI - A Large-Scale Distributed Environment for Peer-to-Peer Services ER - TY - GEN AU - Blesa, Maria J. AU - Blum, Christian AU - de Caro, Angelo AU - Degener, Bastian AU - Kempkes, Barbara AU - Leone, Piere AU - Persiano, Giuseppe AU - Meyer auf der Heide, Friedhelm AU - Mylonas, Georgios ID - 17464 TI - Adapting a sensor net to the dynamic environment in a wildlife scenario - a case study ER - TY - GEN AB - We are given a winding chain of $n$ mobile robots between two stations in the plane, each of them having a limited viewing range. It is only guaranteed that each robot can see its two neighbors in the chain. We analyze a simple and natural parallel strategy to shorten the chain in a time model where each relay is allowed to move up to a distance of $\delta$ in each time step. This model fills the gap between the previously used discrete time model and the continuous time model which was introduced recently in \cite{sirocco}. We analyze the strategy with respect to two quality measures: the number of time steps and the maximum distance to be traveled by the robots, which are the major energy consumers in this scenario. We provide asymptotically tight or almost tight bounds in this time model for both quality measures and it turns out that the best choice for $\delta$ is $\delta \in \Theta(\frac{1}{n})$, since this minimizes the number of time steps as well as the maximum traveled distance. AU - Brandes, Philipp AU - Degener, Bastian AU - Kempkes, Barbara AU - Meyer auf der Heide, Friedhelm ID - 17586 TI - Building short chains of mobile robots locally with a bounded stepwidth ER - TY - CONF AU - Bar-Yehuda, Reuven AU - Polevoy, Gleb AU - Rawitz, Dror ID - 17665 T2 - DIALM-PODC TI - Bandwidth allocation in cellular networks with multiple interferences ER - TY - CHAP AU - Hamann, Heiko AU - Schmickl, Thomas AU - Stradner, Jürgen AU - Crailsheim, Karl AU - Levi, Paul AU - Kernbach, Serge ID - 18761 T2 - Symbiotic Multi-Robot Organisms: Reliability, Adaptability, Evolution TI - Hormone-based Control for Multi-modular Robotics ER - TY - THES AU - Bienkowski, Marcin ID - 18910 SN - 978-3-942647-01-4 TI - Page migration in dynamic networks VL - 282 ER - TY - THES AU - Dynia, Miroslaw ID - 18927 SN - 978-3-942647-03-8 TI - Collective graph exploration VL - 284 ER - TY - JOUR AU - Degener, Bastian AU - Gehweiler, Joachim AU - Lammersen, Christiane ID - 19011 IS - 3 JF - Algorithmica SN - 0178-4617 TI - Kinetic Facility Location VL - 57 ER - TY - CONF AU - Gehweiler, Joachim AU - Meyerhenke, Henning ID - 19013 SN - 9781424465330 T2 - Proceeedings of 24th International Parallel and Distributed Processing Symposium (IPDPS, HPGC) TI - A distributed diffusive heuristic for clustering a virtual P2P supercomputer ER - TY - CONF AB - Load balancing is an important requirement for the efficient execu-tion of parallel numerical simulations. In particular when the simulation domainchanges over time, the mapping of computational tasks to processors needs tobe modified accordingly. State-of-the-art libraries for this problem are basedon graph repartitioning. They have a number of drawbacks, including the opti-mized metric and the difficulty of parallelizing the popular repartitioning heuris-tic Kernighan-Lin (KL).Here we further explore the very promising diffusion-based graph partitioningalgorithm DIBAP (Meyerhenke et al., JPDC 69(9):750–761, 2009) by adaptingDIBAP to the related problem of load balancing. Experiments with graph se-quences that imitate adaptive numerical simulations demonstrate the applicabilityand high quality of DIBAP for load balancing by repartitioning. Compared to thefaster state-of-the-art repartitioners PARMETIS and parallel JOSTLE, DIBAP’ssolutions have partitions with significantly fewer external edges and boundarynodes and the resulting average migration volume in the important maximumnorm is also the best in most cases.We also prove that one of DIBAP’s key components optimizes a relaxed versionof the minimum edge cut problem. Moreover, we hint at a distributed algorithmbased on ideas used in DIBAP for clustering a virtual P2P supercomputer. AU - Gehweiler, Joachim AU - Meyerhenke, Henning ID - 19016 T2 - Dagstuhl Seminar Proceedings 10261: Algorithm Engineering TI - On Dynamic Graph Partitioning and Graph Clustering using Diffusion ER - TY - GEN AU - Thies, Michael AU - Gehweiler, Joachim ID - 19018 TI - Thread Migration and Checkpointing in Java ER - TY - CONF AU - Kernbach, Serge AU - Schmickl, Thomas AU - Hamann, Heiko AU - Stradner, Jürgen AU - Schlachter, Florian AU - Schwarzer, Christopher s. F. AU - Winfield, Alan F. T. AU - Matthias, Rene ID - 19023 T2 - Artificial Life XII (ALife XII) TI - Adaptive Action Selection Mechanisms for Evolutionary Multimodular Robotics ER - TY - CONF AU - Briest, Patrick AU - Chalermsook, Parinya AU - Khanna, Sanjeev AU - Laekhanukit, Bundit AU - Nanongkai, Danupon ID - 19029 SN - 0302-9743 T2 - Workshop on Internet and Network Economics (WINE) TI - Improved Hardness of Approximation for Stackelberg Shortest-Path Pricing ER - TY - JOUR AU - Meyer auf der Heide, Friedhelm AU - Scheideler, Christian ID - 1903 IS - 5 JF - Informatik Spektrum TI - Algorithmische Grundlagen verteilter Speichersysteme ER - TY - CONF AU - Briest, Patrick AU - Chawla, Shuchi AU - Kleinberg, Robert AU - Weinberg, S. Matthew ID - 19033 SN - 9780898717013 T2 - Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms TI - Pricing Randomized Allocations ER - TY - THES AU - Mahlmann, Peter ID - 19041 SN - 978-3-942647-02-1 TI - Peer-to-peer networks based on random graphs VL - 283 ER - TY - THES AU - Degener, Bastian ID - 19042 SN - 978-3-939350-97-2 TI - Local, distributed approximation algorithms for geometric assignment problems VL - 278 ER - TY - CONF AB - 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. AU - Fischer, Matthias AU - Jähn, Claudius AU - Suess, Tim ID - 18136 T2 - Eurographics Symposium on Parallel Graphics and Visualization (EGPGV) TI - Asynchronous Parallel Reliefboard Computation for Scene Object Approximation ER - TY - CONF AB - Many professional cluster systems consist of nodes with different hardware configurations. Such heterogeneous environments require different load-balancing techniques than homogenous environments. The c-load-collision-protocol is able to achieve good results for data-management purposes. Using this protocol, we propose a way for load-balancing in interactive rendering environments. For this work, we implemented a parallel rendering system and took different picking strategies into account to compare the results. The advantage of our approach compared to other approaches is that we group the available nodes of a cluster into two different categories, based on the hardware abilities. Some nodes are used solely for rendering, while others serve as secondary storage and to assist the former ones by performing auxiliary calculations. AU - Suess, Tim AU - Wiesemann, Timo AU - Fischer, Matthias ID - 18289 SN - 9781424481330 T2 - 2010 IEEE Fifth International Conference on Networking, Architecture, and Storage TI - Evaluation of a c-Load-Collision-Protocol for Load-Balancing in Interactive Environments ER - TY - CHAP AB - Typischerweise sind die Knoten eines PC-Clusters nicht mit leistungsfähigen Grafikkarten ausgestattet. Dennoch bieten Cluster-Betreiber einige wenige Rechenknoten an, die mit Highend-Grafikkarten ausgestattet sind, um beispielsweise eine PowerWall zu betreiben. Wenn zwischen diesen unterschiedlichen Knotentypen ein schnelles Netzwerk existiert, kann die Bilderzeugung durch die Knoten mit schwacher Grafikkarte beschleunigt werden. Dabei können die unterschiedlichen Knotentypen unterschiedliche Aufgabe bearbeiten. In einem solchen heterogenen System, müssen die unterschiedlichen entstehenden Lasten auf andere Weise verteilt werden, als in einem System, bei dem alle Knoten gleich ausgestattet sind. Wir präsentieren in dieser Arbeit Lastbalancierungsmechanismen, die in einem parallelen Out-of-Core-Renderingsystem für heterogene PC-Cluster eingesetzt werden. AU - Suess, Tim AU - Wiesemann, Timo AU - Fischer, Matthias ID - 18290 T2 - Augmented & Virtual Reality in der Produktentstehung TI - Gewichtetes c-Collision-Protokoll zur Balancierung eines parallelen Out-of-Core-Renderingsystems ER - TY - CONF AU - Meyer auf der Heide, Friedhelm AU - Phillips, Cynthia A. ID - 16414 SN - 9781450300797 TI - Proceedings of the 22nd ACM symposium on Parallelism in algorithms and architectures - SPAA '10 ER - TY - CHAP AB - We present an approach for real-time rendering of complex 3D scenes consisting of millions of polygons on limited graphics hardware. In a preprocessing step, powerful hardware is used to gain fine granular global visibility information of a scene using an adaptive sampling algorithm. Additively the visual influence of each object on the eventual rendered image is estimated. This influence is used to select the most important objects to display in our approximative culling algorithm. After the visibility data is compressed to meet the storage capabilities of small devices, we achieve an interactive walkthrough of the Power Plant scene on a standard netbook with an integrated graphics chipset. AU - Eikel, Benjamin AU - Jähn, Claudius AU - Fischer, Matthias ID - 16505 SN - 0302-9743 T2 - Advances in Visual Computing TI - Preprocessed Global Visibility for Real-Time Rendering on Low-End Hardware ER - TY - CHAP AU - Degener, Bastian AU - Kempkes, Barbara AU - Kling, Peter AU - Meyer auf der Heide, Friedhelm ID - 16365 SN - 0302-9743 T2 - Structural Information and Communication Complexity TI - A Continuous, Local Strategy for Constructing a Short Chain of Mobile Robots ER - TY - CONF AU - Degener, Bastian AU - Kempkes, Barbara AU - Meyer auf der Heide, Friedhelm ID - 16401 SN - 9781450300797 T2 - Proceedings of the 22nd ACM symposium on Parallelism in algorithms and architectures - SPAA '10 TI - A local O(n2) gathering algorithm ER - TY - BOOK ED - Abramsky, Samson ED - Gavoille, Cyril ED - Kirchner, Claude ED - Meyer auf der Heide, Friedhelm ED - Spirakis, Paul G. ID - 16403 SN - 0302-9743 TI - Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part II. ER - TY - BOOK ED - Abramsky, Samson ED - Gavoille, Cyril ED - Kirchner, Claude ED - Meyer auf der Heide, Friedhelm ED - Spirakis, Paul G. ID - 16404 SN - 0302-9743 TI - Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part I. ER - TY - THES AU - Lürwer-Brüggemeier, Katharina ID - 19605 TI - Mächtigkeit und Komplexität von Berechnungen mit der ganzzahligen Division VL - 261 ER - TY - THES AU - Mense, Mario ID - 19614 SN - 978-3-939350-79-8 TI - On Fault-Tolerant Data Placement in Storage Networks VL - 260 ER - TY - THES AU - Kortenjan, Michael ID - 19617 SN - 978-3-939350-77-4 TI - Size Equivalent Cluster Trees - Rendering CAD Models in Industrial Scenes VL - 258 ER - TY - THES AU - Bonorden, Olaf ID - 19618 SN - 978-3-939350-76-7 TI - Versatility of Bulk Synchronous Parallel Computing: From the Heterogeneous Cluster to the System on Chip VL - 257 ER - TY - GEN AU - Bonorden, Olaf AU - Degener, Bastian AU - Pietrzyk, Peter AU - Kempkes, Barbara ID - 19722 TI - Complexity and approximation of a geometric local robot assignment problem ER - TY - CHAP AB - We introduce a geometric multi-robot assignment problem. Robots positioned in a Euclidean space have to be assigned to treasures in such a way that their joint strength is sufficient to unearth a treasure with a given weight. The robots have a limited range and thus can only be assigned to treasures in their proximity. The objective is to unearth as many treasures as possible. We investigate the complexity of several variants of this problem and show whether they are in $\classP$ or are $\classNP$-complete. Furthermore, we provide a distributed and local constant-factor approximation algorithm using constant-factor resource augmentation for the two-dimensional setting with $\bigO(\log^*n)$ communication rounds. AU - Bonorden, Olaf AU - Degener, Bastian AU - Kempkes, Barbara AU - Pietrzyk, Peter ID - 19724 SN - 0302-9743 T2 - Algorithmic Aspects of Wireless Sensor Networks TI - Complexity and Approximation of a Geometric Local Robot Assignment Problem ER - TY - GEN AB - Categorizing peer-to-peer networks from an algorithmic point of view the two extremes of the spectrum are unstructured networks and networks based on plain distributed hash tables (DHT). Unstructured networks stand out with their simplicity, robustness, and support for complex queries. Though, they lack efficient query algorithms providing guarantees. On the other hand, DHT based networks feature efficient lookup algorithms with typically logarithmic hop distance and provide simple and efficient load balancing. Yet, they are limited to exact match queries and in many cases hard to maintain under churn. AU - Schindelhauer, Christian AU - Mahlmann, Peter AU - Janson, Thomas ID - 19825 TI - 3nuts: A Locality-Aware Peer-to-Peer Network Combining Random Networks, Search Trees, and DHTs ER - TY - JOUR AU - Ooi, Chia Ching AU - Schindelhauer, Christian ID - 19830 JF - Mobile Networks and Applications (MONET) SN - 1383-469X TI - Minimal Energy Path Planning for Wireless Robots ER - TY - JOUR AU - Ooi, Chia Ching AU - Schindelhauer, Christian ID - 19831 JF - Telecommunication Systems SN - 1018-4864 TI - Utilizing detours for energy conservation in mobile wireless networks VL - 43 ER - TY - CONF AU - Raptopoulos, Christoforos L. AU - Nikoletseas, Sotiris E. AU - Spirakis, Paul G. ID - 19901 SN - 9781493928637 T2 - 34st International Symposium on Mathematical Foundations of Computer Science TI - Colouring Non-sparse Random Intersection Graphs ER - TY - CONF AU - Nikoletseas, Sotiris E. AU - Raptopoulos, Christoforos L. AU - Spirakis, Paul G. ID - 19904 T2 - Proceedings of IPDPS - IEEE International Parallel & Distributed Processing Symposium TI - Combinatorial Properties for Efficient Communication in Distributed Networks with Local Interactions ER - TY - CONF AU - Deveci, Deniz AU - Kortenjan, Michael AU - Schomaker, Gunnar ID - 19934 T2 - Parallel and Distributed Computing and Systems, Nr. 21 TI - Distributed Heterogeneous Hashing and Deterministic Dynamical Decompositions ER - TY - CONF AB - One of the prominent challenges in mobile robotics is to develop control methodologies that allow the adaptation to dynamic and unforeseen environments. The classic approach of hand-coded controllers is very efficient for well-defined tasks and specific environments but poor in adapting to changing environmental conditions. One alternative approach is the application of evolutionary algorithms which need, in turn, easily evolvable representations of controllers. In this paper, we investigate one promising approach of an artificial hormone system as a control paradigm which is believed to be easily optimized by evolutionary processes. In a first step of this research, we focus on the simple task of collision avoidance. We present a brief mathematical analysis of this controller approach and an implementation of the controller on a mobile robot to check the feasibility in principle of our approach. The task is successfully accomplished and we conclude with a discussion of the hormone dynamics in the robot. AU - Stradner, Jürgen AU - Hamann, Heiko AU - Schmickl, Thomas AU - Crailsheim, Karl ID - 20254 SN - 9781424438037 T2 - 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems TI - Analysis and implementation of an Artificial Homeostatic Hormone System: A first case study in robotic hardware ER - TY - JOUR AB - 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. AU - Schmickl, Thomas AU - Hamann, Heiko AU - Wörn, Heinz AU - Crailsheim, Karl ID - 20255 IS - 9 JF - Robotics and Autonomous Systems SN - 0921-8890 TI - Two different approaches to a macroscopic model of a bio-inspired robotic swarm VL - 6 ER - TY - CONF AU - Hamann, Heiko AU - Troch, Inge AU - Breitenecker, F. ID - 20259 T2 - MATHMOD 2009 - 6th Vienna International Conference on Mathematical Modelling TI - Pattern Formation as a Transient Phenomenon in the Nonlinear Dynamics of a Multi-Agent System ER - TY - JOUR AU - Meyer auf der Heide, Friedhelm AU - Rammig, Franz-Josef ID - 17453 JF - Public Service Review: Science and Technology TI - Self-Organisation and Self-Optimization VL - 04 ER - TY - JOUR AU - Briest, Patrick ID - 19031 IS - 1 JF - it - Information Technology SN - 1611-2776 TI - Algorithmische und komplexitätstheoretische Aspekte kombinatorischer Preisoptimierung (Computational Aspects of Combinatorial Pricing Problems) VL - 51 ER - TY - CHAP AB - 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. AU - Briest, Patrick AU - Hoefer, Martin AU - Gualà, Luciano AU - Ventre, Carmine ID - 23744 SN - 0302-9743 T2 - Lecture Notes in Computer Science TI - On Stackelberg Pricing with Computationally Bounded Consumers ER - TY - CONF AB - 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. AU - Laroque, Christoph AU - Fischer, Matthias AU - Dangelmaier, Wilhelm ID - 18138 T2 - European Simulation and Modelling Conference (ESM 2009) TI - Concepts for Model Verification and Validation during Simulation Runtime ER - TY - CHAP AU - Suess, Tim AU - Fischer, Matthias AU - Huber, Daniel AU - Laroque, Christoph AU - Dangelmaier, Wilhelm ID - 18291 T2 - Augmented & Virtual Reality in der Produktentstehung TI - Ein System zur aggregierten Visualisierung verteilter Materialflusssimulationen VL - 252 ER - TY - CONF AB - 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