Algorithms and Complexity

With the increasing size of data, heterogeneous data sources, and unreliable networks, uncertainties in the input data arise, and it is often no longer realistic to assume full knowledge of the input; for example travel times in shortest-path and travelling salesman problems not only depend on the distance, but also on external influences like weather conditions and traffic of other network users. Some of the edges might even completely fail. Within this Research Training Group, we study uncertainty from various angles: robust algorithms, algorithmic game theory, graph kernels, computational social choice and certifying algorithms. Robust algorithms are able to handle uncertainties in the input data while delivering optimal or almost optimal solutions. Many applications require robust algorithms, for example in railway operations research. It is a huge challenge to take long-term decisions on the design of railway networks, train-schedules, and construction periods that are robust in the sense that they allow for efficient re-scheduling and re-routing. But even tiny little changes in the input data can lead to arbitrarily bad and even infeasible solutions. From the theoretical viewpoint, the design of robust algorithms is a formidable challenge which seems to need fundamentally new algorithmic techniques and insights. Algorithmic game theory provides a general approach to dealing with uncertainties and incomplete information in multi-agent systems, such as multi-robot systems. Within this research thrust, robust algorithms for packing problems, dispatching in railway systems, and computational social choice will be developed. Robust versions of graph kernels, an important technique in machine learning to deal with graph-structured data, will be developed. Certification is a pragmatic approach to deal with all kinds of uncertainties that may lead to the failure of an algorithm: together with a solution it requires to deliver a certificate witnessing the correctness of the solution. The following subsections describe five sample dissertation projects within the research thrust Algorithms and Complexity.