Jonas Knoll, Universität Paderborn
30. März 2011, 14:00 Uhr, F1.110
Lokale Gathering-Strategie mit begrenzter Schrittweite
Ein Schwerpunkt bei der Forschung über Schwärme autonomer Roboter ist es herauszufinden welche Fähigkeiten benötigt werden um bestimmte Aufgaben zu erfüllen. Ein sehr grundlegendes Problem ist das Gathering Problem. Dieses befasst sich mit einer Gruppe von autonomen Robotern, welche auf einer Ebene verteilt sind und sich auf einem nicht vordefinierten Punkt versammeln sollen. Es gibt bereits viele Strategien, die dieses Problem für verschiedene Modelle (Roboter und Zeit) lösen, es sind aber nur wenige Laufzeitschranken bekannt. In diesem Vortrag wir eine lokale Strategie für Roboter mit begrenzter Sicht- und Schrittweite präsentiert, welche auf einem Paper aus dem Projekt Smart Teams basiert. Die Roboter aus dem Paper haben bereits eine beschränkte Sichtweite (Kreis von Radius 2) und sind oblivious, können also keine Informationen speichern. Als Zeitmodell wird das weit verbreitete asynchrone Runden Modell verwendet, bei dem Zeit in diskrete Schritte unterteilt wird und in jedem Schritt nur ein Roboter aktiv ist. Für die Strategie wurde eine erwartete maximale Laufzeit von O(n²) gezeigt. Im neuen Modell ist die Schrittweite der Roboter auf 0<d<=1 pro Zeitschritt beschränkt. Um weiterhin eine Laufzeitschranke zeigen zu können, muss allerdings die oblivious-Beschränkung gelockert werden. Die erwartete Laufzeit von der neuen Strategie ist durch O(n²/d³) beschränkt, wobei Tests einen geringeren Einfluss von d erwarten lassen.
(Abschlussvortrag Bachelorarbeit)
Martin Dietzfelbinger, TU Ilmenau
14. März 2011, 14:00 Uhr, F1.110
Evolutionäre Algorithmen und Small-World-Netzwerke
Im Vortrag werden zwei Szenarien betrachtet:
1) Eine sehr einfache randomisierte, "evolutionäre" Suchstrategie zum Suchen des Minimums einer Funktion auf {1,...,n}. Man beginnt an einem zufälligen Punkt und würfelt (gemäß einer Verteilung mu) eine Distanz zu einem neuen Punkt aus, an dem die Funktion ausgewertet wird. Falls sich eine Verbesserung ergibt, geht man zu dem besseren neuen Punkt. Dies wird iteriert. Wenn die Funktion unimodal ist (erst fallend, dann steigend), sind O((log n)2) Funktionsauswertungen hinreichend (günstige Verteilung mu) und Omega((log n)2) viele notwendig.
2) Ein 2000 von Jon M. Kleinberg vorgeschlagenes Modell zur Untersuchung des "Small-World-Phänomens": Zu einem einfachen Basisnetzwerk mit n Knoten (etwa einem ein- oder zweidimensionalen Gitter) werden für jeden Knoten zufällig gewählte "Fernkanten" hinzugefügt, uniform, d.h. von der Position des Knotens unbeeinflusst. Die erwartete Anzahl von Kanten pro Knoten ist 1. Was ist nun die maximale Anzahl von Schritten zwischen zwei Knoten in dem resultierenden Netzwerk bei einer extrem einfachen ("greedy") Reisestrategie: man wählt in jedem Schritt den erreichbaren Knoten, der am nächsten am Zielknoten liegt? Man weiß seit längerem, dass dies bei günstiger Verteilung der Länge der Fernkanten O((log n)2) ist. Im Vortrag wird ein relativ neues Ergebnis vorgestellt, das zeigt, dass bei beliebiger Verteilung für die Fernkanten Omega((log n)2) eine untere Schranke ist.
Die numerische Ähnlichkeit der Ergebnisse springt ins Auge. Gibt es einen Zusammenhang zwischen evolutionären Algorithmen und "Small-World"-Netzwerken?
Chrsitian Sohler, Technische Universität Dortmund
22. Februar 2011, 13:30 Uhr, F1.110
Property Testing in Bounded Degree Graphs
Property testing is a relaxation of a standard decision task. Given access to an object (for example, a graph, a function or a point set) we would like to decide with probability at least 2/3, whether the object has a certain property (for example, bipartiteness, monotonicity or convex position) or is far away from the property. The goal is to solve this relaxed decision task by looking at a small (sublinear) part of the object.In this talk I will summarize recent work on property testing in the bounded-degree graph model for sparse graphs.
Carsten Rösnick, Universität Paderborn
21. Februar 2011, 14:00 Uhr, F1.110
Approximate Real Function Maximization and Query Complexity
Using a discrete approach to real computation, even seemingly easy problems like function maximization MAX(f) = max_{0 \leq t \leq X} f(t) might eventually become hard. We are interested in the root (for say, the analytic properties of the input function) causing the complexity of MAX. For that, we determine parameterized bounds on the complexity of approximate func- tion maximization. To date, this question appears to be unexamined. However, answering it helps exploiting the problem’s inner structure with respect to notions of classical analysis like Lipschitz continuity. Moreover, an answer also is of practical interest concerning implemen- tations on existing frameworks for exact real arithmetic. We conduct a two step approach. First, we devise different ways of accessing an unknown continuous real function via protocol (i.e., oracle) queries. These protocols are compared to each other regarding their simula- tion complexity, along with an analysis of their computability and computational complexity. Second, we determine the query complexity of approximating the MAX-functional relative to selected protocols. It is found that the simulation complexity often depends on the function’s Lipschitz constant (besides other notions of sufficiently steep or flat functions), whereas for the query complexity it is necessary to reveal this constant to any simulation algorithm as long as non-adaptive information is concerned. On the contrary, no such limitation holds when considered adaptive information and access to a range approximating protocol.
(Abschlussvortrag Masterarbeit, Vortragssprache Deutsch)
Robert Gmyr, Universität Paderborn
16. Februar 2011, 14:00 Uhr, F1.110
Das Three Distance Theorem und dessen Anwendung im
Kontext von Hash TablesSei s eine beliebige irrationale Zahl. Das Three Distance Theorem besagt, dass durch die Platzierung der Punkte {s}, {2s},..., {ns}, wobei {x} der Nachkommateil von x ist, also {x} = x - \floor{x}, auf dem Liniensegment [0..1], n+1 Liniensegmente von höchstens drei unterschiedlichen Längen entstehen. Dieses Theorem begründet eine besondere Eigenschaft von Hash Tables, welche die Multiplikationsmethode zur Erzeugung von Hash Funktionen nutzen: Mit gleichbleibendem Abstand aufeinander folgende Schlüssel, wie sie in der Praxis häufig auftreten, werden in der Hash Table gleichmäßig verteilten Speicherstellen zugeordnet. Dadurch wird die Anzahl der Kollisionen, die solche Schlüssel erzeugen, minimiert. Diese Eigenschaft sowie das Three Distance Theorem bilden zusammen eine „Perle der theoretischen Informatik“ und werden in dieser Arbeit erläutert und bewiesen.
(Vortrag im Rahmen des Seminars »Perlen der Theoretischen Informatik«)
Florentin Neumann, Universität Paderborn
16. Februar 2011, 15:00 Uhr, F1.110
Local Computation of Spanners with Slack
A graph spanner is sparse representation of a graph such that distances between pairs of nodes are maintained within a small multiplicative stretch. The efficient construction of sparse, low-stretch spanners is essential for many theoretical and practical applications. Recently, the concept of 'Slack Spanners' has been introduced, which allows the sequential computation of spanners that have size linear in the number of nodes, while achieving constant stretch for a large fraction of the pairwise distances. The objective of my master thesis is to devise and to analyze local algorithms that compute spanners with slack in the distributed 'Congest Model'.
(Antrittsvortrag Masterarbeit, Vortragssprache Deutsch)
Ralf Petring, Universität Paderborn
9. Februar 2011, 14:00 Uhr, F1.110
Multi Algorithm Rendering
There are many rendering algorithmsknown in computer graphics. Each of them performs well for a specific type of scene but they may perform poorly on other types of scenes. The problem we consider in this talk are scenes which consist of different scene types combined in a single scene. For such scenes there is no single optimal algorithm. We present an idea how to use many algorithms in a single frame to display different parts of the scene. At this we consider sampled observer positions to find the best out of a given set of algorithms for the different scene parts. We consider culling algorithms as well as approximation algorithms. In this talk we focus on approximation algorithms and how to deside which to use for the different scene parts to get the best image quality.
Tim Süß, Universität Paderborn
9. Februar 2011, 14:30 Uhr, F1.110
Parallel Out-of-Core Occlusion Culling
We present a parallel rendering system for PC-Clusters to visualize large 3D scenes. One single visualization node, equipped with a high-end graphics adapter, is supported by a group of back-end nodes with weak graphics performance. The objects of the scene are distributed among these back-end nodes, they serve two purposes: First, they provide an out-of-core memory system for the visualization node. Second, they assist the visualization node's rendering by performing visibility calculations and only sending visible objects to the visualization node. In order to obtain fast rendering with our system, we have to distribute the objects among the back-end nodes in a way that does not only guarantee an even distribution of the objects, but also an even distribution of the visibility calculations and the amount of data send to the visualization node. We identify necessary properties of the distribution and argue that a random distribution is a good candidate. Further, in order to reduce the number of objects sent to the visualization node per frame, we employ an approximate hierarchical occlusion culling in each back-end node. For this, they are equipped, in addition to the objects assigned to them, with simplified versions of the other objects of the 3D scene. The visualization node is equipped with 512 MiB video memory and supported by 15 back-end nodes. This system is able to render a 350 million polygons (about 8.5 GiB) large aircraft model between 20 - 30 fps and thus allows a walkthrough in real-time.
Peter Kling, Universität Paderborn
19. Januar 2011, 14:00 Uhr, F1.110
Collisionless Gathering of Robots with an Extent
In the first part, I give a talk to be held on January 27, 2011 at the 37th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM). We consider the well-studied gathering problem, but with the additional twist of non-zero sized robots. Problems such as collisions and deadlocks arise, making it rather hard to model and to analyze this problem. Thus, our theoretical work uses a relatively simple, discretized model and features experimental results to both motivate our ongoing research and to establish a relation to a more realistic setting.
In the second part, I give a short overview about and discuss ongoing joint work with Martina Hüllmann and Andreas Koutsopoulos about Self-adjusting Nanostructures. Although this work uses a very similar model and similar ideas, the motivation originates from a completely different area.
Hendrik Renken, Universität Paderborn
12. Januar 2011, 16:00 Uhr, F1.544
Event-based asymptotic time complexity of simulations of discrete event systems
In this talk we propose an upper bound for the event-based time complexity of the simulation of generic DES models. To determine the upper bound we constructed a special simulation algorithm for which we can (over-)estimate the number of events processed during a simulation run and the overall runtime costs one event generates.
Sascha Brandt, Universität Paderborn
15. Dezember 2010, 14:00 Uhr, F1.110
Visibility Distance: Analysis and Applications
Visibility in computer graphics is a wide spread topic and there are many algorithms out there, which are calculating the visibility of an object in realtime or in a preprocessing step. More rarely is the examination of objects that are about to be visible, i.e. that becomes visible in the near future while moving through a virtual scene. For this purpose the visibility distance is introduced in this dissertation. An informal definition of the visibility distance could be: "The shortest distance, a viewer has to cover, until a given object becomes visible." If the visibility distance is computed, it can be used to improve out-of-core pre-fetching algorithms.
(Abschlussvortrag Bachelorarbeit, Vortragssprache Deutsch)
Torsten Bruns, Universität Paderborn
15. Dezember 2010, 14:45 Uhr, F1.110
Planung optimaler Trajektorien mittels diskreter Mathematik (am Beispiel des autonomen Kreuzungsmanagements für Kraftfahrzeuge)
In dem Vortrag wird ein Verfahren vorgestellt, mit dem für niedrigdimensionale Systeme optimale und kollisionsfreie Trajektorien berechnet werden können. Im Rahmen der Optimierung können unterschiedliche Zielgrößen berücksichtigt werden, die ihren Ausdruck allerdings in Form einer Wunsch- bzw. Soll-Trajektorie finden müssen. Sowohl bei der Modellierung als auch bei der Lösung des zuvor skizzierten Problems werden Methoden aus dem Bereich der diskreten Mathematik angewendet. Dies ermöglicht eine Abschätzung und Skalierung des Berechnungsaufwands, was wiederum eine gute Eignung für die Anwendungen unter Echtzeitbedingungen bedeutet.
Das Verfahren wird am Beispiel des autonomen Kreuzungsmanagements eingeführt und bewertet: Für autonome Fahrzeuge, die als lineare dynamische Systeme 2. Ordnung modelliert werden, werden kollisionsfreie Trajektorien für die Überquerung einer Kreuzung bzw. eines beliebigen Verkehrsknotenpunktes berechnet. Bei der Berechnung werden Optimierungszielgrößen wie Dauer, Komfort und Kraftstoffverbrauch berücksichtigt.
Prinzipiell kann das Verfahren auf beliebige gleichartige Anwendungen übertragen werden, wie zum Beispiel auf die Trajektorienplanung von Robotern mit gemeinsamem Arbeitsraum.
Peter Pietrzy, Universität Paderborn
8. Dezember 2010, 14:00 Uhr, F1.110
Local Approximation Algorithms for Facility Location Problems
We provide an overview of sequential approximation algorithms for various kinds of the Facility Location Problem and present ideas how to execute these algorithms in a distributed setting. The main focus lies on the aspect of locality and the algorithms' ability to deal with changes in the given problem instance.
Carsten Rösnick, Universität Paderborn
1. Dezember 2010, 14:00 Uhr, F1.110
Approximate Real Function Maximization and Query Complexity
Frameworks like iRRAM [1] or RealLib [2] allow to compute approximations of continuous functions within prescribed error bounds. The study of the computational complexity of continuous problems when only given partial information about the input is called information-based complexity [3]. Taking the approximation of continuous problems one step further, i.e., looking at real functionals L : (IR -> IR) -> IR, especially raises the question about its computational complexity in such frameworks. It is one goal of this Master's Thesis to determine the complexity of approximating the maximization functional MAX(f) := max_{x \in [0,1]} f(x) by varying the information given about f, which is not complete, but partial and contaminated [3]. In combination with a complexity analysis of computing the information itself, this should yield more explicit quantitative and parameterized both upper and lower bounds (compared to [4]) on the complexity of MAX.- [1] Norbert Th. Müller. The iRRAM: Exact arithmetic in C++. Computability and Complexity in Analysis, pages 222–252, 2001.
- [2] B. Lambov. RealLib: An efficient implementation of exact real arithmetic, Mathematical Structures in Computer Science, 17(01):81-98, 2007.
- [3] J.F. Traub, G.W. Wasilkowski, and H. Wozniakowski. Information-Based Complexity, 1988.
- [4] Ker-I. Ko and Harvey Friedman. Computational complexity of real functions. Theoretical Computer Science, 20(3):323–352, 1982.
(Antrittsvortrag Masterarbeit)
(Vortragssprache Deutsch)
Benjamin Eikel, Universität Paderborn
17. November 2010, 14:00 Uhr, F1.110
Preprocessed Global Visibility for Real-Time Rendering on Low-End Hardware
In the first part I will talk about the paper mentioned below, which I am going to present at November 30, 2010 at the 6th International Symposium on Visual Computing (ISVC 10). In the second part I give an outlook for my future work on rendering algorithms and data structures for mobile devices. I will give a short insight into our implementation for the Android mobile operating system. Furthermore I will mention some level-of-detail and out-of-core techniques that are planned to improve the existing system.
Abstract. 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 ?ne granular global visibility information of a scene using an adaptive sampling algorithm. Additively the visual in?uence of each object on the eventual rendered image is estimated. This in?uence 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.
joint work with: Claudius Jähn, Matthias Fischer
Barbara Kempkes, Universität Paderborn
10. November 2010, 14:00 Uhr, F1.110
Gathering mobile robots locally in time O(n^4)
Gathering mobile robots in one not predetermined point in the Euclidean plane is a classical problem from the area of robot formation problems. In the last fifteen years, a lot of effort has been put into pinpointing the set of crucial capabilities which the robots must have in order to achieve gathering in finite time. So far, only a few runtime bounds are known. Some bounds exist for algorithms in a global setting, and there is also one algorithm with known runtime bounds for robots with a local viewing range which uses rather strong robots. We show that gathering is also possible in time O(n^4) with very weak robots which only have a local viewing range.
Christiane Lammersen, Techische Universität Dortmund
10. November 2010, 14:45 Uhr, F1.110
Approximation Techniques for Facility Location and its Application in Metric Embeddings
Andreas Cord-Landwehr, Universität Paderborn
3. November 2010, 14:00 Uhr, F1.110
The Dynamic Facility Location Problem in Geometric Settings
Clustering can play a critical role in increasing life-time and performance of wireless networks. Equipped with the movement of network nodes, limited visibility, and mixed sending and receiving costs, there are several issues to be handled at the same time and which make a difference to the common facility location problem. This Master's thesis presents a generalization of a recent work by Degener, Kempkes, and Pietrzyk to solve the facility location problem in the power-of-metrics case, as well as for several scenarios with inaccurate distance measurements and node movements. The result is a state-of-the-art constant factor approximation with stabilization time logarithmic in the number of nodes.(Abschlussvortrag Masterarbeit)
(Vortragssprache Deutsch)
Sebastian Abshoff, Universität Paderborn
11. Oktober 2010, 16:15 Uhr, F0.231
Evaluation of Distributed, Local Approximation Algorithms for the Facility Location Problem
Recently a distributed and local algorithm that achieves a 17-approximation for the uncapacitated metric facility location problem was published by Degener, Kempkes and Pietrzyk. The necessary improvement steps to obtain a (3+epsilon)-approximation as well as results of the performance analysis are explained in this presentation.
(Abschlussvortrag Bachelorarbeit)
