Peter Kling, University of Paderborn

May 16, 2012, 2:00 pm, F1.110

Energy-aware Scheduling - Take a Break and Hold Your Competitive Factor Tight

I present two recent research results. Both consider an energy-aware scheduling scenario where tasks of a certain size and value arrive over time. If a task is not finished until its deadline, we have to pay a penalty equal to its value. Our scheduler decides which job to process at any time and how much energy to invest. The more energy invested, the faster it is finished. The cost of a schedule is the sum of penalty and invested energy.

The first result combines two known energy-saving techniques (speed scaling and sleep states). We show that this combination introduces a new difficulty. Especially, standard scheduling techniques no longer yield a constant competitiveness, but can become arbitrarily bad. We tackle the reason for this decrease, showing that a job's value density (ratio between value and work) is a crucial parameter. While we are not yet able to provide more elaborate algorithms that do not suffer from this drawback, we analyze a combination of two standard algorithms and prove a nearly optimal competitive factor depending on the maximum value density.

The second result drops the sleep state from the model. For this case, Chan, Lam, and Li (2010) presented a scheduling strategy that is $\alpha^{\alpha}+2e\alpha$-competitive, where $\alpha$ is a constant determining the power consumption of the processor. Their analysis is based on a standard technique involving a sophisticated potential function. I present a new analysis of (essentially) the same algorithm yielding a tight competitiveness of $\alpha^{\alpha}$. The analysis is based on duality theory for convex programs and not only yields a much simpler proof, but also this improved, best possible competitive factor. Moreover, in contrast to the potential function based analysis, my technique may allow a relatively easy generalization to the multi-processor case.

Claudius Jähn, University of Paderborn

May 9, 2012, 2:00 pm, F1.110

Applied 3D computer graphics -- project status report

In order to visualize and interact with complex, three-dimensional objects in a virtual environment, excessive manual preparations of the data may be necessary. While the visualization of complex data for itself can be a challenging task already, the creation of animations, or the simulation of behavior of the virtual objects usually requires expert knowledge. Supporting the user with new tools and interaction techniques helps to reduce this obstacle when using 3D computer graphics in an industrial context.

In this talk, I am going to present the status of current project plans in which we are planning to work in the described context.

Project Group NODES, University of Paderborn

April 25, 2012, 2:00 pm, F1.110

Offering Dynamics to Emerging Structures

During the past year, the project group NODES focused on local strategies in dynamic networks. We chose four different problems in which participants of a network have to act in a local way and need to cope with dynamics caused by adversaries, so called external dynamics. Modifications initiated by the participants themselves are referred to as controlled dynamics. We analyzed a new variant of the facility location problem in which facilities are allowed to move and clients dynamically change their demand. We compared an online algorithm to the optimal offline algorithm and were able to proof a competitive ratio of sqrt(2)+1. Another problem dealt with rearranging nodes on a line and in a tree such that frequently communicating nodes are close together. For the line, we introduced several classes of algorithms and analyzed their powerfulness. For the tree, we provide some experimental results. Another study aimed at a self-stabilizing topology which provides short distances between nodes and a constant degree. Furthermore, we evaluated different ways to introduce external and controlled dynamics to the weak coloring problem.

Sebastian Abshoff, University of Paderborn

April 11, 2012, 2:00 pm, F1.110

Capabilities and Limitations of Distributed Computational Models for Highly-Dynamic Networks

A dynamic network is modeled as a dynamic graph G_r=(V,E_r), where V is a static set of nodes and E_r is the set of links in round r. Nodes have IDs and, in the worst case, the topology may change arbitrarily from round to round as long as the network stays connected in every round. A node may broadcast a message in round r which is delivered to its neighbors in round r+1. This talk gives a short introduction to the work by Kuhn et al. on fundamental problems in this model such as counting, k-verification, k-token dissemination, and all-to-all token dissemination.

Starting from this, the goal of my Ph.D. project is to understand, model, and classify different, more specific types of dynamics. A classification could be based on the complexity of performing benchmark tasks like all-to-all token dissemination. This talk gives an overview about problems and questions I want to analyze in my research project.