@techreport{19688,
abstract = {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.},
author = {Briest, Patrick and Goldberg, Paul W. and Roeglin, Heiko},
title = {{Approximate Equilibria in Games with Few Players}},
year = {2008},
}
@misc{19950,
author = {Pietrzyk, Peter},
title = {{Lokale Strategien zur Optimierung von Kommunikationsketten}},
year = {2008},
}
@phdthesis{20262,
author = {Hamann, Heiko},
isbn = {9783642133763},
issn = {1867-4925},
title = {{Space-Time Continuous Models of Swarm Robotic Systems}},
doi = {10.1007/978-3-642-13377-0},
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},
}
@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},
}
@phdthesis{19615,
author = {Schomaker, Gunnar},
isbn = {978-3-939350-78-1},
title = {{Distributed Resource Allocation and Management in Heterogeneous Networks}},
year = {2008},
}
@inproceedings{19812,
abstract = {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.},
author = {Schindelhauer, Christian and Mahlmann, Peter},
booktitle = {The European Integrated Project "Dynamically Evolving, Large Scale Information Systems (DELIS), Proceedings of the Final Workshop},
number = {222},
pages = {1--22},
publisher = {Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn},
title = {{Random Graphs for Peer-to-Peer Overlays}},
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},
}
@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