Research Seminar

Print
Peter Kling

May 22, 2013, 2:00 pm, F1.110

Augmenting Your Analysis-Arsenal for Online Problems

Algorithms for online problems have to deal with the lack of knowledge about future events. While  sometimes it is possible to come up with online algorithms that are not too bad when compared to an optimal offline solution, more often than not the price one has to pay for not being clairvoyant is rather high. Resource augmentation formalizes the idea of compensating for the lack of knowledge by more speed, more memory, .... Typically one is interested to quantify in how far this more "something" can make up for the missing knowledge about the future.

In my talk I consider a relatively new kind of resource augmentation recently suggested by S. Albers and M. Hellwig. The basic idea is to allow online algorithms to generate more than one (but essentially independent) online solutions and to charge only for the best one. Depending on the problem at hand this can be seems as augmenting the system with more machines or more space, but this approach can also be applied to more general situations. I present some of the results by Albers and Hellwig to give an example of this approach. They consider the makespan minimization problem, one of the most fundamental optimization and scheduling problems. At the end, I give a short outline of problems that I think are promising candidates for this approach.

Stefan Heindorf

May 8, 2013, 2:00 pm, F1.110

Dispersion of Multi-Robot Teams

The robot gathering problem has been studied extensively in various variants. This master's thesis aims to do the opposite and disperse the robots. Many applications require the robots to spread out, for example, in order explore an unknown terrain or to cover a large area with sensors. The first step towards this goal will be to place the robots close together on a one dimensional line and to develop and analyze algorithms to distribute the robots uniformly in a fixed distance. The second step will be to do the same in two dimensions: initially, the robots are close together in the two dimensional plane and they should form a straight line with a fixed distance between them. Interesting properties that might be studied via simulation and theoretical analysis are whether the robots actually converge to a straight line and how long it takes. The last step will be to generalize the algorithms and analysis techniques. One idea might be to reverse the gathering algorithm, i.e., maximize the minimal distance between robots, and see if it is suited for the dispersion problem.

(Introductory presentation of master's thesis, talk in English)

Barbora Candrakova

April 24, 2013, 2:00 pm, F1.110

The circular chromatic index of $k$-regular graphs

The circular chromatic index of a graph $G$ is the infimum of all rational numbers $p/q$, such that there exists a circular $p/q$-edge-coloring of the graph $G$. It is an interesting problem to determine the set of possible values of the circular chromatic index of $k$-regular graphs.

In this work we construct $k$-regular graphs with certain circular chromatic indices of the form $k+a/p$, in particular graphs for all $a \in \{1,2,\ldots,\lfloor k/2 \rfloor\}$ and $p\ge 2a^2+a+1$.

Project Group Cloud3D

April 17, 2013, 2:00 pm, F1.110

Algorithms for 3D Rendering using Cloud Computing

Modern technology led to tablets and smartphones as more portable versions of workstations and even laptops. However, storage and computational power is still limited. Rendering complex 3D scenes is a challenging problem on these devices when using conventional methods. Our project group addressed highly complex scenes, by creating a remote rendering system, providing mobile devices with support from a cloud.
We developed a hybrid rendering algorithm for low performance devices, which uses point-based and standard polygon rendering simultaneously. An additional mechanism tries to automatically modify the renderer's parameters, depending on the available processing power. To complement the rendering system, we implemented the client and server side of a network service, providing different functionalities to support the mobile device.

(Final Report)

Christoph Weddeman

April 10, 2013, 2:00 pm, F1.110

Roboterschwarmbewegungen auf einem Gitter

A Crowd of fishes is a swarm. Although there are thousands of individuals, they act and move like one global unit. Each fish can only see and therefore influence a small part of the swarm. If there is one fish leading the swarm, then the question is how do the others get to know the direction to move?
We adapt this problem for swarm theory and consider a swarm of indistinguishable robots on a two dimensional grid. One robot is assigned as a leader, and has additional knowledge of a fixed path. The leader moves on this route, and the other robots shall follow him, without losing connection of the swarm. In this master thesis we will get to know the problem, and take a look at first ideas for moving strategies. Thus we want our robots to use only local information, we will see what difficul-ties may arise.

(Final presentation Master Thesis, talk in German)