@proceedings{16431, editor = {{Meyer auf der Heide, Friedhelm and Bender, Michael A.}}, isbn = {{9781605586069}}, title = {{{Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures - SPAA '09}}}, doi = {{10.1145/1583991}}, year = {{2009}}, } @article{16398, author = {{Bienkowski, Marcin and Byrka, Jaroslaw and Korzeniowski, Miroslaw and Meyer auf der Heide, Friedhelm}}, issn = {{1570-8667}}, journal = {{Journal of Discrete Algorithms}}, pages = {{545--569}}, title = {{{Optimal algorithms for page migration in dynamic networks}}}, doi = {{10.1016/j.jda.2008.07.006}}, year = {{2009}}, } @phdthesis{19615, author = {{Schomaker, Gunnar}}, isbn = {{978-3-939350-78-1}}, publisher = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}}, title = {{{Distributed Resource Allocation and Management in Heterogeneous Networks}}}, volume = {{259}}, year = {{2008}}, } @inproceedings{19686, author = {{Briest, Patrick}}, booktitle = {{Proceedings of the 35th InternationalColloquium on Automata, Languages and Programming (ICALP)}}, isbn = {{9783540705741}}, issn = {{0302-9743}}, title = {{{Uniform Budgets and the Envy-Free Pricing Problem}}}, doi = {{10.1007/978-3-540-70575-8_66}}, year = {{2008}}, } @inproceedings{19687, author = {{Briest, Patrick and Krysta, Piotr and Babaioff, Moshe}}, booktitle = {{Proceedings of the 1st International Symposium on Algorithmic Game Theory (SAGT)}}, title = {{{On the Approximability of Combinatorial Exchange Problems}}}, doi = {{https://doi.org/10.1007/978-3-540-79309-0_9}}, year = {{2008}}, } @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}}, } @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}}, } @inproceedings{19813, abstract = {{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. }}, author = {{Ooi, Chia Ching and Schindelhauer, Christian}}, booktitle = {{MWCN'08: Proc. of IFIP Joint Conference on Mobile Wireless Communications Networks (MWCN 2008) and Personal Wireless Communications (PWC 2008)}}, isbn = {{9780387848389}}, issn = {{1571-5736}}, publisher = {{Springer}}, title = {{{Detours Save Energy in Mobile Wireless Networks}}}, doi = {{10.1007/978-0-387-84839-6_6}}, year = {{2008}}, } @inproceedings{19832, author = {{Ooi, Chia Ching and Schindelhauer, Christian}}, booktitle = {{ARS'08: Proc. of the 9th International Symposium on Distributed Autonomous Robotic Systems (DARS 2008)}}, isbn = {{9783642006432}}, title = {{{Energy-Efficient Distributed Target Tracking Using Wireless Relay Robots}}}, doi = {{10.1007/978-3-642-00644-9_4}}, 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}}, } @unpublished{26235, abstract = {{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).}}, author = {{Ziegler, Martin and Koolen, Wouter M.}}, booktitle = {{arXiv:0802.2027}}, title = {{{Kolmogorov Complexity Theory over the Reals}}}, year = {{2008}}, } @inproceedings{26243, abstract = {{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.}}, author = {{Köhler, Sven and Ziegler, Martin}}, booktitle = {{Proc. 8th Conference on Real Numbers and Computers}}, pages = {{147--156}}, title = {{{On the Stability of Fast Polynomial Arithmetic}}}, year = {{2008}}, } @article{26255, abstract = {{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.}}, author = {{Ziegler, Martin}}, journal = {{Applied Mathematics and Computation}}, title = {{{Physically-Relativized Church-Turing Hypotheses}}}, year = {{2008}}, } @inbook{26262, author = {{Ziegler, Martin}}, booktitle = {{Verhandlungen der Deutschen Physikalischen Gesellschaft}}, pages = {{145}}, publisher = {{Deutsche Physikalische Gesellschaft (DPG)}}, title = {{{A Meta-Theory of Physics and Computation}}}, year = {{2008}}, } @article{26280, author = {{Meer, Klaus and Ziegler, Martin}}, issn = {{0885-064X}}, journal = {{Journal of Complexity}}, pages = {{3--15}}, title = {{{An explicit solution to Post's Problem over the reals}}}, doi = {{10.1016/j.jco.2006.09.004}}, year = {{2008}}, } @inproceedings{17416, abstract = {{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. }}, author = {{Suess, Tim and Huber, Daniel and Fischer, Matthias and Laroque, Christoph and Dangelmaier, Wilhelm}}, booktitle = {{IEEE International Symposium on Parallel and Distributed Processing with Applications}}, isbn = {{9780769534718}}, title = {{{A System for Aggregated Visualization of Multiple Parallel Discrete Event Simulations}}}, doi = {{10.1109/ispa.2008.30}}, year = {{2008}}, } @inproceedings{17868, abstract = {{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. }}, author = {{Dangelmaier, Wilhelm and Fischer, Matthias and Huber, Daniel and Laroque, Christoph and Suess, Tim}}, booktitle = {{2008 Winter Simulation Conference}}, isbn = {{9781424427079}}, pages = {{2012--2020}}, title = {{{Aggregated 3D-visualization of a distributed simulation experiment of a queuing system}}}, doi = {{10.1109/wsc.2008.4736296}}, year = {{2008}}, } @inproceedings{19003, author = {{Degener, Bastian and Gehweiler, Joachim and Lammersen, Christiane}}, booktitle = {{Proceedings of the 11th Scandinavian Workshop on Algorithm Theory (SWAT)}}, isbn = {{9783540699002}}, issn = {{0302-9743}}, pages = {{378--389}}, title = {{{The Kinetic Facility Location Problem}}}, doi = {{10.1007/978-3-540-69903-3_34}}, year = {{2008}}, } @inproceedings{19004, abstract = {{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.}}, author = {{Gehweiler, Joachim and Lammersen, Christiane and Degener, Bastian}}, booktitle = {{Proceedings of the 24th European Workshop on Computational Geometry}}, pages = {{251--254}}, title = {{{The Kinetic Facility Location Problem}}}, year = {{2008}}, }