@inproceedings{1940, author = {{Mense, Mario and Scheideler, Christian}}, booktitle = {{Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20-22, 2008}}, pages = {{1135----1144}}, publisher = {{SIAM}}, title = {{{SPREAD: an adaptive scheme for redundant and fair storage in dynamic heterogeneous storage systems}}}, year = {{2008}}, } @inproceedings{20367, author = {{Hamann, Heiko and Wörn, Heinz}}, booktitle = {{The tenth International Conference on Simulation of Adaptive Behavior (SAB'08)}}, isbn = {{9783540691334}}, issn = {{0302-9743}}, pages = {{447----456}}, title = {{{Aggregating Robots Compute: An Adaptive Heuristic for the Euclidean Steiner Tree Problem}}}, doi = {{10.1007/978-3-540-69134-1_44}}, volume = {{5040}}, year = {{2008}}, } @inproceedings{20368, abstract = {{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.}}, author = {{Hamann, Heiko and Schmickl, Thomas and Wörn, Heinz and Crailsheim, Karl}}, booktitle = {{IEEE/RSJ 2008 International Conference on Intelligent Robots and Systems (IROS'08)}}, pages = {{1415----1420}}, publisher = {{IEEE Press}}, title = {{{Spatial Macroscopic Models of a Bio-Inspired Robotic Swarm Algorithm}}}, doi = {{10.1109/IROS.2008.4651038}}, year = {{2008}}, } @article{20369, abstract = {{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.}}, author = {{Hamann, Heiko and Wörn, Heinz}}, issn = {{1935-3812}}, journal = {{Swarm Intelligence}}, number = {{2-4}}, pages = {{209--239}}, title = {{{A framework of space–time continuous models for algorithm design in swarm robotics}}}, doi = {{10.1007/s11721-008-0015-3}}, volume = {{2}}, year = {{2008}}, } @inbook{17978, author = {{Lürwer-Brüggemeier, Katharina and Ziegler, Martin}}, booktitle = {{Unconventional Computing}}, isbn = {{9783540851936}}, issn = {{0302-9743}}, title = {{{On Faster Integer Calculations Using Non-arithmetic Primitives}}}, doi = {{10.1007/978-3-540-85194-3_11}}, year = {{2008}}, } @inproceedings{18139, abstract = {{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. }}, author = {{Laroque, Christoph and Fischer, Matthias and Dangelmaier, Wilhelm and Eikel, Benjamin}}, booktitle = {{Industrial Simulation Conference (ISC 2008)}}, pages = {{306--310}}, publisher = {{EUROSIS-ETI}}, title = {{{Dynamic Control of Animation Schemes for the Efficient 3D-Visualization of Material Flow Simulations}}}, year = {{2008}}, } @inproceedings{18141, abstract = {{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.}}, author = {{Laroque, Christoph and Fischer, Matthias and Eikel, Benjamin}}, booktitle = {{Augmented & Virtual Reality in der Produktentstehung}}, pages = {{193----206}}, publisher = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}}, title = {{{Regelung von Animationen in Simulationen von hochdynamischen Fabrikszenen }}}, volume = {{232}}, year = {{2008}}, } @article{18143, author = {{Le Roux, Stéphane and Ziegler, Martin}}, issn = {{1571-0661}}, journal = {{Electronic Notes in Theoretical Computer Science}}, pages = {{73--88}}, title = {{{Singular Coverings and Non-Uniform Notions of Closed Set Computability}}}, doi = {{10.1016/j.entcs.2008.03.009}}, year = {{2008}}, } @article{18570, abstract = {{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.}}, author = {{Ackermann, Heiner and Briest, Patrick and Fanghänel, Alexander and Vöcking, Berthold}}, isbn = {{9783540771043}}, journal = {{Internet Mathematics}}, number = {{4}}, pages = {{459--475}}, publisher = {{Springer}}, title = {{{Who Should Pay for Forwarding Packets?}}}, doi = {{10.1007/978-3-540-77105-0_21}}, volume = {{5}}, year = {{2008}}, } @inbook{16463, author = {{Meyer auf der Heide, Friedhelm and Schneider, Barbara}}, booktitle = {{Biologically-Inspired Collaborative Computing}}, isbn = {{9780387096544}}, issn = {{1571-5736}}, title = {{{Local Strategies for Connecting Stations by Small Robotic Networks}}}, doi = {{10.1007/978-0-387-09655-1_9}}, year = {{2008}}, } @inbook{16464, author = {{Gehweiler, Joachim and Meyer auf der Heide, Friedhelm}}, booktitle = {{Taschenbuch der Algorithmen}}, isbn = {{9783540763932}}, title = {{{Bin Packing oder „Wie bekomme ich die Klamotten in die Kisten?“}}}, doi = {{10.1007/978-3-540-76394-9_40}}, year = {{2008}}, } @unpublished{16465, abstract = {{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