Algorithms and Complexity

The group focusses both in research and teaching on following topics:• randomized algorithms• approximation and online algorithms• algorithms for interconnection networks• probabilistic analysis of algorithms• algorithmic game theoryApproachesforthedesignofalgorithmicsolutionstohardproblemsaremanifold. Foroptimization problems, a very suitable concept is that of approximation algorithms,whereonetriestoobtainprovablygoodsolutionsfortheproblem, inthesensethatthecost of the computed solution is at most a fraction apart from the cost of the optimalone. Another approach is to apply randomized algorithms, which are designed to givean optimal (or good approximative) solution with high probability. Besides positiveresults as in the design of algorithms, also the according hardness results with respectto the particular concepts are of high interest, since they guide the way for appropriatealgorithmic approaches.Inmanyapplicationstheinputdataforagivenoptimizationproblemisnotcompletelygiveninadvance,butisrevealedstepbystep. Nevertheless,thealgorithmmustalreadymake decisions based on the partial input only. Typical problems in this area includefor instance elevator movement planning and paging strategies. These algorithms arereferred to as online algorithms and their performance can be evaluated by comparingtheir solutions to an optimal offline strategy, i.e., a strategy for which the completeinput for the problem is assumed to be known in advance.In particular, the merge of economic game theory and algorithmics for modellingproblems arising for instance in today’s networks opens a completely new field of al-gorithmicresearchandreceivedalotofattentioninrecentyears. Here,onefocusisonthecomparisonbetweenthecostofoptimalsolutionsobtainedbygloballycoordinatedoperators on one hand and the cost of equilibria yielded by selfish agents on the otherhand. Another focus is the design of algorithms for optimization problems, where theinput data is not necessarily reliable, as it is given by selfish agents. In this setting, thegoal is to design algorithms solving the optimization problem and additionally forcingthe agents to “reveal” the true input data — “algorithms” of these types are usuallydenoted as mechanisms. In this context, the analysis and design of auctions, and inparticular of combinatorial auctions, reveals interesting insights.Besides classes concerning the above mentioned topics, the department regularly of-fers courses on algorithmic cryptography and parallel algorithms.72