TY - CONF AB - In this paper we present and analyze HSkip+, a self-stabilizing overlay network for nodes with arbitrary heterogeneous bandwidths. HSkip+ has the same topology as the Skip+ graph proposed by Jacob et al. [PODC 2009] but its self-stabilization mechanism significantly outperforms the self-stabilization mechanism proposed for Skip+. Also, the nodes are now ordered according to their bandwidths and not according to their identifiers. Various other solutions have already been proposed for overlay networks with heterogeneous bandwidths, but they are not self-stabilizing. In addition to HSkip+ being self-stabilizing, its performance is on par with the best previous bounds on the time and work for joining or leaving a network of peers of logarithmic diameter and degree and arbitrary bandwidths. Also, the dilation and congestion for routing messages is on par with the best previous bounds for such networks, so that HSkip+ combines the advantages of both worlds. Our theoretical investigations are backed by simulations demonstrating that HSkip+ is indeed performing much better than Skip+ and working correctly under high churn rates. AU - Feldotto, Matthias AU - Scheideler, Christian AU - Graffi, Kalman ID - 412 T2 - Proceedings of the 14th IEEE International Conference on Peer-to-Peer Computing (P2P) TI - HSkip+: A Self-Stabilizing Overlay Network for Nodes with Heterogeneous Bandwidths ER - TY - THES AB - In meiner Dissertation besch{\"a}ftige ich mich mit dem Entwurf und der Analyse energieeffizienter Schedulingalgorithmen, insbesondere f{\"u}r sogenannte Speed-Scaling Modelle. Diese stellen das theoretische Pendant von Techniken wie AMDs PowerNOW! und Intels SpeedStep dar, welche es erlauben die Geschwindigkeit von Prozessoren zur Laufzeit an die derzeitigen Bedingungen anzupassen. Theoretische Untersuchungen solcher Modelle sind auf eine Arbeit von Yao, Demers und Shenker (FOCS'95) zur{\"u}ckzuf{\"u}hren. Hier kombinieren die Autoren klassisches Deadline-Scheduling mit einem Prozessor der Speed-Scaling beherrscht. Es gilt Jobs verschiedener Gr{\"o}ße fristgerecht abzuarbeiten und die dabei verwendete Energie zu minimieren. Der Energieverbrauch des Prozessors wird durch eine konvexe Funktion $\POW\colon\R_{\geq0}\to\R_{\geq0}$ modelliert, welche die Geschwindigkeit auf den Energieverbrauch abbildet.Meine Dissertation betrachtet verschiedene Varianten des urspr{\"u}nglichen Speed-Scaling Modells. Forschungsrelevante Ergebnisse sind in den Kapiteln 3 bis 6 zu finden und erstrecken sich {\"u}ber die im Folgenden beschriebenen Aspekte:- Kapitel 3 und 4 betrachten verschiedene \emph{Price-Collecting} Varianten des Originalproblems. Hier d{\"u}rfen einzelne Deadlines verfehlt werden, sofern eine jobabh{\"a}ngige Strafe gezahlt wird. Ich entwerfe insbesondere Online-Algorithmen mit einer beweisbar guten Competitiveness. Dabei liefern meine Ergebnisse substantielle Verbesserungen bestehender Arbeiten und erweitern diese unter Anderem auf Szenarien mit mehreren Prozessoren.- In Kapitel 5 wird statt des klassischen Deadline-Schedulings eine Linearkombination der durchschnittlichen Antwortzeit und des Energieverbrauchs betrachtet. Die Frage, ob dieses Problem NP-schwer ist, stellt eine der zentralen Forschungsfragen in diesem Gebiet dar. F{\"u}r eine relaxierte Form dieser Frage entwerfe ich einen effizienter Algorithmus und beweise seine Optimalit{\"a}t.- Das letzte Kapitel betrachtet ein Modell, welches – auf den ersten Blick – nicht direkt zur Speed-Scaling Literatur z{\"a}hlt. Hier geht es stattdessen um ein allgemeines Resource-Constrained Scheduling, in dem sich die Prozessoren zusammen eine gemeinsame, beliebig aufteilbare Ressource teilen. Ich untersuche die Komplexit{\"a}t des Problems und entwerfe verschiedene Approximationsalgorithmen. AU - Kling, Peter ID - 431 TI - Energy-efficient Scheduling Algorithms ER - TY - CONF AB - We give a polynomial time algorithm to compute an optimal energy and fractional weighted flow trade-off schedule for a speed-scalable processor with discrete speeds.Our algorithm uses a geometric approach that is based on structural properties obtained from a primal-dual formulation of the problem. AU - Antoniadis, Antonios AU - Barcelo, Neal AU - Consuegra, Mario AU - Kling, Peer AU - Nugent, Michael AU - Pruhs, Kirk AU - Scquizzato, Michele ID - 435 T2 - Proceedings of the 31st Symposium on Theoretical Aspects of Computer Science (STACS) TI - Efficient Computation of Optimal Energy and Fractional Weighted Flow Trade-off Schedules ER - TY - BOOK ED - Flocchini, Paola ED - Gao, Jie ED - Kranakis, Evangelos ED - Meyer auf der Heide, Friedhelm ID - 16870 SN - 0302-9743 TI - Algorithms for Sensor Systems - 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, {ALGOSENSORS} 2013 VL - 8243 ER - TY - CHAP AU - Lukovszki, Tamás AU - Meyer auf der Heide, Friedhelm ID - 16394 SN - 0302-9743 T2 - Lecture Notes in Computer Science TI - Fast Collisionless Pattern Formation by Anonymous, Position-Aware Robots ER - TY - CHAP AU - Abshoff, Sebastian AU - Meyer auf der Heide, Friedhelm ID - 16395 SN - 0302-9743 T2 - Structural Information and Communication Complexity TI - Continuous Aggregation in Dynamic Ad-Hoc Networks ER - TY - JOUR AU - Mertsching, Bärbel AU - Divband Soorati, Mohammad AU - Kotthauser, Tobias ID - 19981 JF - IEEE International Conference on Robotics and Biomimetics (ROBIO) TI - Automatic Reconstruction of Polygonal Room Models from 3D Point Clouds ER - TY - JOUR AU - Hamann, Heiko AU - Karsai, Istvan AU - Schmickl, Thomas ID - 20148 IS - 7 JF - Bulletin of Mathematical Biology TI - Time delay implies cost on task switching: A model to investigate the efficiency of task partitioning VL - 75 ER - TY - JOUR AU - Hamann, Heiko AU - Schmickl, Thomas AU - Stradner, Jürgen AU - Crailsheim, Karl AU - Thenius, Ronald AU - Zahadat, Payam ID - 20150 JF - Chaos, Solitons & Fractals TI - Algorithmic Requirements for Swarm Intelligence in Differently Coupled Collective Systems VL - 50 ER - TY - CONF AU - Hamann, Heiko AU - Schmickl, Thomas AU - Stradner, Jürgen AU - Schwarzer, Christopher AU - Michiels, Nico K. AU - Esparcia-Alcazar, Anna Isabel ID - 20151 T2 - Applications of Evolutionary Computation - 16th European Conference (EvoApplications 2013) TI - Virtual Spatiality in Agent Controllers: Encoding Compartmentalization VL - 7835 ER - TY - CONF AU - Hamann, Heiko ID - 20160 T2 - 7th IEEE Int. Conf. on Self-Adaptive and Self-Organizing Systems (SASO 2013) TI - A Reductionist Approach to Hypothesis-Catching for the Analysis of Self-Organizing Decision-Making Systems ER - TY - CONF AU - Hamann, Heiko AU - Lio, Pietro AU - Miglino, Orazio AU - Nicosia, Giuseppe AU - Nolfi, Stefano AU - Pavone, Mario ID - 20161 T2 - 12th European Conference on Artificial Life (ECAL 2013) TI - Speciation Dynamics: Generating Selective Pressure Towards Diversity ER - TY - JOUR AU - Hamann, Heiko ID - 20162 IS - 3 JF - Swarm Intelligence TI - Towards Swarm Calculus: Urn Models of Collective Decisions and Universal Properties of Swarm Performance VL - 7 ER - TY - CONF AB - Viele virtuelle 3-D-Szenen im industriellen Bereich sind nicht gleichmäßig strukturiert, z.B. weil sie eine stark unterschiedliche Dichteverteilung der Polygone aufweisen. Für solch heterogene Daten existiert kein Algorithmus, der die Gesamtheit der Daten sowohl schnell als auch mit guter Qualität darstellen kann. Die Auswahl der richtigen Algorithmen für einzelne Szenenteile durch einen Experten ist zeitintensiv und in vielen Visualisierungssystemen nicht umzusetzen. Um dieses Problem zu lösen, setzt das hier vorgestellte Multi-Algorithmen-Rendering verschiedene Renderingalgorithmen gleichzeitig ein, um eine virtuelle 3-D-Szene darzustellen. Das Verfahren unterteilt die Szene dafür in einem Vorverarbeitungsschritt automatisch in geeignete Teilregionen und bestimmt deren Eigenschaften. Diese Daten werden zur Laufzeit dazu genutzt, um ständig für den aktuellen Standpunkt des Betrachters eine Abschätzung der Qualität und Laufzeit der zur Auswahl stehenden Renderingalgorithmen zu berechnen. Durch die Lösung eines Optimierungsproblems kann so bei vorgegebener Bildrate durch die passende Zuordnung der Algorithmen zu den Regionen die Bildqualität optimiert werden – bei automatischer Anpassung an die Leistungsfähigkeit der eingesetzten Hardware. In einer experimentellen Evaluierung vergleichen wir die Laufzeit und Bildqualität des Verfahrens mit denen verbreiteter Standardrenderingverfahren. AU - Petring, Ralf AU - Eikel, Benjamin AU - Jähn, Claudius AU - Fischer, Matthias AU - Meyer auf der Heide, Friedhelm ID - 17439 T2 - 11. Paderborner Workshop Augmented & Virtual Reality in der Produktentstehung TI - Darstellung heterogener 3-D-Szenen in Echtzeit VL - 311 ER - TY - THES AU - Eikel, Benjamin ID - 17440 TI - Spherical visibility sampling : preprocessed visibility for occlusion culling in complex 3D scenes ER - TY - CONF AU - Meyer auf der Heide, Friedhelm ID - 17442 T2 - 11. Paderborner Workshop Augmented & Virtual Reality in der Produktentstehung TI - Algorithmische Grundlagen für die Selbstorganisation von Roboterschwärmen VL - 311 ER - TY - GEN ED - Gausemeier, Jürgen ED - Grafe, Michael ED - Meyer auf der Heide, Friedhelm ID - 17443 TI - 11. Paderborner Workshop Augmented & Virtual Reality in der Produktentstehung VL - 311 ER - TY - JOUR AB - In this paper, we define and study a new problem, referred to as the Dependent Unsplittable Flow Problem (D-UFP). We present and discuss this problem in the context of large-scale powerful (radar/camera) sensor networks, but we believe it has important applications on the admission of large flows in other networks as well. In order to optimize the selection of flows transmitted to the gateway, D-UFP takes into account possible dependencies between flows. We show that D-UFP is more difficult than NP-hard problems for which no good approximation is known. Then, we address two special cases of this problem: the case where all the sensors have a shared channel and the case where the sensors form a mesh and route to the gateway over a spanning tree. AU - Cohen, R. AU - Nudelman, I. AU - Polevoy, Gleb ID - 17663 IS - 5 JF - Networking, IEEE/ACM Transactions on KW - Approximation algorithms KW - Approximation methods KW - Bandwidth KW - Logic gates KW - Radar KW - Vectors KW - Wireless sensor networks KW - Dependent flow scheduling KW - sensor networks SN - 1063-6692 TI - On the Admission of Dependent Flows in Powerful Sensor Networks VL - 21 ER - TY - CONF AB - We consider the k-token dissemination problem, where k initially arbitrarily distributed tokens have to be disseminated to all nodes in a dynamic network (as introduced by Kuhn et al., STOC 2010). In contrast to general dynamic networks, our dynamic networks are unit disk graphs, i.e., nodes are embedded into the Euclidean plane and two nodes are connected if and only if their distance is at most R. Our worst-case adversary is allowed to move the nodes on the plane, but the maximum velocity v_max of each node is limited and the graph must be connected in each round. For this model, we provide almost tight lower and upper bounds for k-token dissemination if nodes are restricted to send only one token per round. It turns out that the maximum velocity v_max is a meaningful parameter to characterize dynamics in our model. AU - Abshoff, Sebastian AU - Benter, Markus AU - Cord-Landwehr, Andreas AU - Malatyali, Manuel AU - Meyer auf der Heide, Friedhelm ID - 477 T2 - Algorithms for Sensor Systems - 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, {ALGOSENSORS} 2013, Sophia Antipolis, France, September 5-6, 2013, Revised Selected Papers TI - Token Dissemination in Geometric Dynamic Networks ER - TY - CONF AB - We present a new online algorithm for profit-oriented scheduling on multiple speed-scalable processors.Moreover, we provide a tight analysis of the algorithm's competitiveness.Our results generalize and improve upon work by \citet{Chan:2010}, which considers a single speed-scalable processor.Using significantly different techniques, we can not only extend their model to multiprocessors but also prove an enhanced and tight competitive ratio for our algorithm.In our scheduling problem, jobs arrive over time and are preemptable.They have different workloads, values, and deadlines.The scheduler may decide not to finish a job but instead to suffer a loss equaling the job's value.However, to process a job's workload until its deadline the scheduler must invest a certain amount of energy.The cost of a schedule is the sum of lost values and invested energy.In order to finish a job the scheduler has to determine which processors to use and set their speeds accordingly.A processor's energy consumption is power $\Power{s}$ integrated over time, where $\Power{s}=s^{\alpha}$ is the power consumption when running at speed $s$.Since we consider the online variant of the problem, the scheduler has no knowledge about future jobs.This problem was introduced by~\citet{Chan:2010} for the case of a single processor.They presented an online algorithm which is $\alpha^{\alpha}+2e\alpha$-competitive.We provide an online algorithm for the case of multiple processors with an improved competitive ratio of $\alpha^{\alpha}$. AU - Kling, Peter AU - Pietrzyk, Peter ID - 499 T2 - Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) TI - Profitable Scheduling on Multiple Speed-Scalable Processors ER -