Efficient Use of Resources in Parallel Systems

Parallel sorting algorithms and centralized and local load-balancing methods improve the exploit of the performance of parallel systems. In particular, so-called periodic and diffusive load-balancing algorithms can be used successfully as a background procedure to speed up the execution of parallel algorithms that have irregular communication patterns or generate dynamically changing, highly asymmetric load distributions. In this project, we would like to design, analyze and implement efficient load-balancing algorithms, in particular driven by the demand of technical applications from the area of hardware/software morphing and other dynamic systems.

Approximation Algorithms

It is presumed that problems that are shown NP-complete cannot be solved in polynomial time. Nevertheles, solutions to these problems must be found, even if they are not optimal, as long as they can be generated quickly. Besides devising such fast approximation algorithms for combinatorial optimization problems, a considerable art is to determine the quality of the obtained solution in terms of the optimum solution without knowing it. Another important aspect of an approximation algorithm is to present a bad input, a so-called witness, that is an input where the algorithm may output quite a bad feasible solution that is far away from the optimum solution. Especially in the field of the Traveling Salesperson Problem there are some heurists in use where the gap between witnesses and performance guarantees are still considerably large. In this project, we would like to design good witnesses against some of these heuristics.