Summer Term 2011

Manuel Hüster, University of Paderborn

September 28, 2011, 2:00 p.m., F1.110

Efficient pathfinding algrothms for multi-storey three-dimensional buildings

Pathfinding algrothms play in today's world and in several application fields an elemental role. It is accustomed to use an optimistic estimate for calculation the shortest route between two nodes. There are different estimators that meet the efficiency requirements within a two-dimensional environments, such as the Euclidean distance. There was, however, for multi-storey and three-dimensional buildings no analogue functional estimator.

Consequently, in the master work, an approach was developed that calculates an optimistic estimate of an abstracted representation. Here, several realizations are used or developed and compared directly and with the Euclidean distance.The estimates are used by an A * - algorithm with the result that using the estimates from the abstraction gains a more efficient execution than using the Euclidean distance in multi-storey three-dimensional buildings.

(Final Presentation Master Thesis)

Philipp Brandes, University of Paderborn

September 14, 2011, 9:00 a.m., F1.110

Robust Distributed Computation in Dynamic Networks

Consider a distributed computation in a dynamic network with n nodes. We allow the topology of this network to be changed by an adversary in each round but a connected graph must always be maintained. The nodes communicate synchronously via broadcasting to their neighbors in every round. An algorithm for this setting has been presented which is able to correctly count the number of nodes in O(n2).

In this master's thesis we extend the research in that area. We analyze the robustness of the algorithm. The edges in the original model are considered to be reliable. But what happens if errors can occur? To analyze this, a common failure model is added on top of the proposed model. We assume randomized edge failure and examine the consequences on the algorithm and how to adapt it such that it outputs the correct count with high probability. Furthermore, we analyze the robustness of the algorithm if a dynamic set of nodes is introduced and propose changes such that the counting process continues to output a valid value. In addition to the robustness analysis, we briefly explore different network properties which might be used to reduce the run-time of the counting algorithm.

(Final Presentation Master Thesis)

Sven Kurras, University of Paderborn

August 31, 2011, 2:00 p.m., F1.110

Distributed Sampling of Regular Graphs

Generating random graphs, called graph sampling, is used as a tool in various applications as well as of its own theoretical interest. In the context of Peer-to-Peer networks, one is interested in sampling d-regular graphs that provide high connectivity and low diameter while being robust against node failures and adversarial attacks. Distributed strategies are preferred, because any presence of a central server might become a bottleneck and makes such a network vulnerable. Since random graphs do provide the above properties with high probability, a promising distributed strategy is to constantly randomize the connections between the nodes by a simple local operation, aiming to achieve a global structure that is sufficiently close to random. Therefore, one needs to quantify the speed of convergence towards the long-term random distribution, denoted as the mixing time of the underlying Markov chain towards its stationary distribution on all d-regular graphs.

An example for such an operation is k-Flip, where the outer edges of a random (k+2)-walk are interleaved. For k=1, high-polynomial upper-bounds for the mixing time are known, while it is supposed that for n-node graphs O(n log n) should hold. For k>1, the only known bound requires k to be very large, k ∈ Θ(d² n² log 1/ε), which contradicts the locality.

In a first part, this master's thesis investigates the state of the art in distributed sampling of regular graphs. The main focus lies on gaining deep insights into the problem structure as well as on working out the advanced proof techniques, such as canonical paths, Markov chain coupling, graph spectra, and others. So prepared, in a second part, an attempt should be made to find some valuable result for one of the involved problems, for example some mixing time upper bound for k ∈ Θ(log n).

(Introductory Presentation Master Thesis)

Holger Schmeisky, University of Paderborn

August 10, 2011, 2:00 p.m., F1.110

Approximate String Matching (Hamming distance)

Approximate string matching under Hamming distance is a classic problem of computer science. Hamming distance counts the number of mismatching characters between two strings. Applications in bioinformatics need algorithms that are fast for small alphabets. In recent years several average-optimal algorithms were presented and their performance on real inputs is compared in this thesis.

(Final Presentation Bachelor Thesis)

Kathrin Bujna, University of Paderborn

August 3, 2011, 2:00 p.m., F1.110

Learning and Analysing Local Strategies for Self-Organizing Robotic Exploration Teams

We are given an arbitrarily formed chain of mobile relay robots that connects two base stations. Each relay does only know its two neighbours in the chain, which have to be within its viewing range. The goal is to shorten this chain as far as possible. The problem with this is that each relay can base its decision where to move only on the relative position of its neighbours. There already exist local strategies for this setting, such as the Hopper strategy and the Move-on-Bisector strategy.

The master thesis will elaborate on the question whether the existing strategies can be improved. To this end, we will analyse what happens if we change the existing strategies just slightly, and also investigate the gain from extending the abilities of the relays.

(Introductory Presentation Master Thesis)

Andreas Cord-Landwehr, University of Paderborn

July 13, 2011, 2:00 p.m., F1.110

Distributed Search in Huge Networks

We consider networks consisting of clients, servers, and service providers. The servers form the market places at which service providers can offer and where clients search for best fitting services. A client's search query consists of a parametrized evaluation function that states how good a discovered service fits the query. As the network is huge and nodes may leave or join, we are interested in local search strategies for the clients. Contrary to most current literature, in our model it is not possible to organize the services (i.e., the service providers) a priori by a given ordered data structure.

In this talk I present two research approaches that we will examine in this scenario. One approach concentrates on the question on how to locally modify the network (according to recent search requests) to improve costs for future searches. The second approach focuses at the service provider's view: we ask how to advertise the services of a specific service provider best to a group of clients to maximize the gain of the service provider.

The presented research questions are embedded into the upcoming SFB 901 "On-The-Fly Computing". In this collaborative research project we ask the question on how to establish a highly dynamic market of IT services of many participants. A key question there is how to allow efficient searching for IT services. Characteristics of the On-The-Fly market include that every participant can also be a service provider by itself, that participants can join and leave the market, and that participants search for best fitting services (specified by evaluation functions).

Peter Kling, University of Paderborn

July 6, 2011, 2:00 p.m., F1.110

Scheduling Techniques for Large Scale Parallel Computing Systems

Parallelization and concurrency have become standard in today's computing systems. Whether you consider the massive parallelization provided by modern graphic adapters to enable photo-realistic real-time rendering, high performance clusters as those run by Google, Amazon, and Co. to offer large amounts of computational power on demand, or even Maple running on your personal laptop exploiting the parallelism of the build-in quad-core. Without carefully designed parallel architectures as well as sophisticated techniques to utilize the computational resources, these scenarios would hardly be conceivable.

This leads us to the concept of “On-The-Fly Computing” as promoted by the upcoming SFB 901.

It envisions a nearly fully automated market for many different kinds of IT services, including software development, configuration of software based on smaller components, and computational power for a timely execution of configured software services. One key concept of this vision are the so called “On-The-Fly Compute Centers”: a term referring essentially to improved variants of today's compute centers. To cope with the expected computational demand and its timely allocation, such centers must make efficient use of all available, possibly heterogeneous, computational resources.

In my talk, I will survey the current state of scheduling techniques suitable for such large scale computing systems as well as ideas for future research directions. One focus will lie on energy-aware scheduling, as energy has become *the* limiting cost factor for modern compute centers. We will discuss ideas for profitable energy-aware scheduling techniques, i.e., schedulers that incorporate additional Quality of Service constraints into the scheduling decisions.

Fei Teng, University of Paderborn

June 29, 2011, 2:00 p.m., F1.110

Image Error Evaluation

In the field of Computer graphics we often would like to know the display quality of an image or a video. The quality of an image can be determined by comparing it to the original image. Previous researches of image quality mostly focused on evaluating common images that are photo-alike, but here we are interested in the quality of rendered images, where the errors come from approximative rendering algorithms, thus having different characteristics on errors than photos.

A Program that measures image quality in real-time has been developed, it contains decent image quality metrics including those which are taken from previous researches that are considered useful to evaluate quality of photo-alike images, for example measuring luminance / contrast / structural similarity and combine them to the result. Also methods have been implemented which try to compare rendered images, for example using the image pyramid method to determine concentrations of errors.

Tests have shown that there exist huge differences between the results depending on the different characteristics of the error in an image, and none of the implemented metrics was "good for all". Among the implemented metrics, Structural Similarity is the best metric to evaluate common image quality, while Image Pyramid is the best for rendered image quality.

(Final Presentation Bachelor Thesis)

Jörg Meier, University of Paderborn

June 29, 2011, 2:30 p.m., F1.110

A local strategy for maintaining a short chain of robots between a base station and a mobile explorer

We envision a terrain without obstacles where a communication chain of n relays connects a static base station and an arbitrary moving explorer. Further, we enable the explorer to move faster than the maximum speed of a relay. Since the robot moves, the number of relays in the chain may change with time. We study a local strategy, which maintains communication between the explorer and the base and shortens the chain, in combination with two intuitive strategies for insertion.

In a theoretical analysis, we were able to present bounds for the speed of the explorer in a general scenario and state maximum numbers of rounds until a new relay is introduced. Additionally, the performance of these strategies was examined and compared experimentally.

(Final Presentation Bachelor Thesis)

Tobias Tscheuschner, University of Paderborn

June 22, 2011, 2:00 p.m., F1.110

The complexity of local max-cut

Local search is the most effective approach for dealing with hard optimization problems. In local search, one assigns a set of neighbor solutions to every solution and asks for a solution that has no better neighbor solutions, i. e. a local optimum. The neighborhood relation between the solutions naturally induces so called 'standard' algorithms that find a local optimum: begin with a feasible solution and iteratively move to a better neighbor until a local optimum is found. Many empirical and theoretical investigations have shown that local search methods quickly comverge to a local optimum for most instances.

In this talk we study the problem of computing a local optimum for Max-Cut with FLIP-neighborhood, in which exactly one node changes the partition. In particular, we consider three results. First, there are graphs of maximum degree four and initial solutions for these graphs for which every standard algorithm, independent of the pivot rule that choses among the improving solutions, requires exponentially many steps to reach a local optimum. Second, there are graphs of maximum degree four and initial solutions for which finding a local optimum reachable from the initial solution via a standard algorithm is PSPACE-complete. Third, finding a local optimum is PLS-complete for graphs with maximum degree five.

(Research Seminar Workgroup Scheideler )

Robert Gmyr, University of Paderborn

June 15, 2011, 2:00 p.m., F1.110

Exploiting User Behavior for 3D Rendering

The user behavior can have a considerable impact on the performance of rendering algorithms. In out-of-core rendering for example the choice of the set of objects stored in main memory at a given time is crucial for the rendering performance. A bad choice of this set may yield a drop in frame rate because objects have to be loaded from secondary memory. Here, the user behavior can be leveraged to choose a good set of objects: If a user looked at an object frequently in the past, he will probably look at it again in the future. Therefore these frequently viewed objects should be stored in main memory to improve the rendering performance.

The goal of this thesis is to develop a method to exploit user behavior in order to improve rendering algorithms. The method should assign weights to each object of a scene depending on the user behavior. These weights should then be used to improve rendering algorithms, as in the example above.

(Introductory Presentation Master Thesis)

Florentin Neumann, University of Paderborn

June 1, 2011, 2:00 p.m., F1.110

Local Computation of Spanners with Slack

A subgraph spanner of a weighted graph G is a sparse representation that preserves distances approximately between all pairs of nodes. In contrast, a slack spanner of G only preserves a large fraction of the pairwise distances. In this thesis, we present the first known distributed algorithm for computing slack spanners for arbitrary weighted graphs. Given any n-node weighted graph G, the metric space induced by it, its unweighted diameter k, and 0<epsilon<1, it is shown how to locally compute an epsilon-uniform slack spanner of G in the synchronous CONGEST model in O(k) rounds. In this model the maximum message size is limited to O(log(n)) bits. The spanner obtained is a subgraph of G that consists of O(n) edges and guarantees O(1/epsilon)-stretch for all but an epsilon-fraction of the pairwise distances. In contrast, all previous distributed spanner constructions give stretch guarantees on all pairwise distances, but at the expense of increased spanner size. E.g., there are graphs for which those constructions yield O(loglog(n))-spanners of size O(n^{1+1/loglog(n)}), whereas we can obtain O(loglog(n))-stretch spanners of size O(n), in granting this spanner to have an (1/loglog(n))-slack. Although our algorithm's worst case running time depends on the unweighted diameter of the input graph, we give evidence that this is non-trivial within the chosen model. These results are complemented by an algorithm for computing slack spanners on the complete network: Given any arbitrary metric space M=(V,d) of size |V|=n and 0<epsilon<1, we present an algorithm that locally computes a graph spanner for M with epsilon-uniform slack and a constant stretch factor in O(1/epsilon) synchronous rounds.

(Final Presentation Master Thesis)

Kamil Swierkot, University of Paderborn

June 1, 2011, 2:30 p.m., F1.110

Local Distributed Decision

A local algorithm is a distributed algorithm where each processor is a node in a graph and every processor is only capable to communicate with its neighbors.The algorithm is only allowed to make a constant number of communication rounds whereby the message size is not bounded. Between the communication rounds every processor can make arbitrary large computations. Over the last decades a lot of research has been made to find efficient algorithms for several problems in this distributed framework. Thereby reasearchers have produced impressive positive and impossibility results.

But just recently, researchers started to evolve a complexity theory for the local distributed framework in order to classify languages according to their hardness of solving them locally. In their seminal paper [1] Korman et al. introduced nondeterminism on the basis of certificates and local verifiers, complexity classes and local reductions. Like in traditional complexity theory the focus is on decision problems. This talk will give a brief overview of the concepts which will be of interest in my master thesis. Although Korman et al. have proven several structural properties, it is still unknown which languages belong to which complexity class. Therefore my thesis will focus on this aspect.

[1] P. Fraigniaud, A. Korman, and D. Peleg, Local Distributed Decision, Arxiv preprint arXiv:1011.2152 (2010).

(Introductory Presentation Master Thesis)

Andrew Schoenrock, Carleton University

May 18, 2011, 2:00 p.m., F1.110

Parallel methods for protein interaction prediction

Protein-protein interactions play a key role in many human diseases. A detailed knowledge of protein-protein interactions will accelerate the drug discovery process as well as reduce overall drug development costs. Biologists have a variety of methods to determine protein-protein interactions in the laboratory, however these approaches are generally expensive, labour intensive, time consuming and have significantly high error rates. The Protein-protein Interaction Prediction Engine (PIPE) is a computational approach to prediction protein-protein interactions. This talk will discuss the evolution of the PIPE project. The first version of PIPE proved that the underlying hypothesis that the algorithm is built upon had merit. PIPE2 offered a few major performance improvements which allowed for the first proteome-wide, all-to-all protein-protein interaction prediction within the S. Cerevisiae organism (yeast). Although PIPE2 was a significant improvement over the original PIPE, PIPE2 was still plagued an inefficient use of memory and an inability to easily scale to large supercomputers. In MP-PIPE a mixed master-slave/all-slaves parallel model was introduced which allowed for proteome-wide predictions to be made in both the C. Elegans and Homo Sapiens organisms. In addition to these projects, a relatively new project named PIPE-Sites which predicts the actual interaction sites on the proteins using the PIPE output data will also be discussed.

Patrick Briest, University of Paderborn

May 11, 2011, 2:00 p.m., F1.110

The Power of Uncertainty: Bundle-Pricing for Unit-Demand Customers

We study an extension of the unit-demand pricing problem in which a seller may offer bundles of items rather than the individual items for sale. If a customer buys such a bundle, she is guaranteed to receive one of the items contained in it, but the seller does not make any promises as to how the particular item is selected. This model is motivated by the pricing strategy of retailers like hotwire.com, who offers bundles of hotel rooms based on geographic location and star rating, and only identifies the booked hotel after the purchase has been made.

As the selected item is known only in hindsight, the buying decision depends on the customer's belief about the allocation mechanism. We study strictly pessimistic and optimistic customers who always assume the worst-case or best-case allocation mechanism relative to their personal valuations, respectively. While the latter model turns out to be equivalent to the well-studied pure item pricing problem, the former is fundamentally different, and we prove the following results:

(1) A revenue-maximizing pricing can be computed efficiently in the uniform version, in which every customer has a subset of items and the same non-zero value for all items in this subset and a value of zero for all other items.

(2) For non-uniform customers computing a revenue-maximizing pricing is APX-hard.

(3) For the case that any two values of a customer are either identical or differ by at least some constant factor, we present a polynomial time algorithm that obtains a constant approximation guarantee.

This is joint work with Heiko Röglin.

Philipp Brandes, University of Paderborn

May 4, 2011, 2:00 p.m., F1.110

Robust Distributed Computation in Dynamic Networks

Consider a distributed computation in a dynamic network with n nodes. We allow the topology of this network to be changed by an adversary in each round but a connected graph must always be maintained. The nodes communicate synchronously via broadcasting to their neighbors in every round. An algorithm for this setting has been presented which is able to correctly count the number of nodes in O(n²).

But the original algorithm does not deal with robustness. It is assumed that the edges between nodes are reliable. We assume independent, random edge failures. In the master thesis I will try to enhance the algorithm's fault tolerance against this and other types of failures such as network churn.

(Introductory Presentation Master Thesis)

David Maicher, University of Paderborn

April 20, 2011, 2:00 p.m., F1.110

Parameterization of user behaviour for movement within 3D scenes with regard to visibility changes

The aim of this Master thesis is the description of the movement of users within a 3D scene by parameters that are relevant for visibility changes. The influences of individual parameters on visibility are determined within an evaluation. Here are paths considered that are within a fixed scene and match certain parameter values. Information on relevance of the individual parameters can be gained by moving along these paths and measuring the changes in visibility.

(Introductory Presentation Master Thesis ,Talk language is German)

Claudius Jähn, University of Paderborn

April 6, 2011, 2:00 p.m., F1.110

Creating parameterizations for virtual scenes: How to choose the sampling points

The efficiency of rendering algorithms for virtual scenes is influenced by the observer's position in the scene and several properties at that position -- like the amount of occluded geometry. In order to estimate the distribution of such a property globally for all positions in the scene, adaptive sampling techniques can be used. In this talk I am going to present different methods for choosing the positions at which the samples are evaluated, and methods for rating the quality of the resulting sampling distributions.