Invited Speakers

* Marco E. Lübbecke (RWTH Aachen University)

Marco Lübbecke is a full professor for operations research at RWTH Aachen University, Germany. He received his Ph.D. in applied mathematics from TU Braunschweig in 2001 and held positions as assistant professor for combinatorial optimization and graph algorithms at TU Berlin and as visiting professor for discrete optimization at TU Darmstadt.

Marco's research interests are in computational integer programming and discrete optimization. A particular focus is on decomposition approaches to exactly solving large-scale real-world optimization problems. With his appreciation for the beauty of mathematics, and being an editor of OR journals and PC member of algorithms conferences, he finds that the most fascinating challenges are interdisciplinary in nature.

Automatic Decomposition and Branch-and-Price: A Status Report

In this talk, we give an overview of our recent efforts to automatize Dantzig-Wolfe reformulation and column generation/branch-and-price for structured, large-scale integer programs. We present the need for and the benefits from a generic implementation which does not need any user interaction or expert knowledge. A focus is on detecting structures in integer programs which are amenable to a Dantzig-Wolfe reformulation. We give computational results and discuss future research topics.

* Friedhelm Meyer auf der Heide (University of Paderborn)

Friedhelm Meyer auf der Heide is Full Professor in the Computer Science Department and the Heinz Nixdorf Institute at the University of Paderborn. He received his PhD in Mathematics in Bielefeld and his Habilitation in Computer Science in Frankfurt. After a 2-years stay in Dortmund as an Associate Professor he moved to Paderborn in 1989. His research interests include algorithmic and complexity theoretical problems about parallel computing, communication and data management in networks, dynamics in networks, algorithmic foundations on robotic exploration and formation problems, algorithms in computer graphics, and probabilistic analysis, His research is described in more than 150 publications. He was the coordinator of European integrated project DELIS and the CRC “Massively Parallel Computing”, and currently coordinates the newly founded CRC “On-The-Fly Computing”, both financed by the “Deutsche Forschungsgemeinschaft” (DFG). In 1992 he received the Leibniz research award of the DFG together with Burkhard Monien. Since 2007, he is member of the German Academy of Science LEOPOLDINA.

Continuous Local Strategies for Robotic Formation Problems

We consider a scenario with a team of autonomous mobile robots which are placed in the plane. Their goal is to move in such a way that they eventually reach a prescribed formation. Such a formation may be a straight line between two given endpoints (Robot Chain Problem), a circle or any other geometric pattern, or just one point (Gathering Problem). In this survey, we assume that there is no central control that guides the robot's decisions, thus the robots have to self-organize in order to accomplish global tasks like the above-mentioned formation problems. Moreover, we restrict them to simple local strategies: the robots are limited to "see" only robots within a bounded viewing range; their decisions where to move next are solely based on the relative positions of robots within this range. Most strategies for these type of problems assume a discrete time model, i.e., time is divided into rounds, in a round, each robot moves to some target point de ned by the observations of its environment.

In this talk, we focus on a much less examined class of local strategies, namely continuous strategies. Here, each robot continuously observes his environment and continuously adapts its speed and direction to these observations. focus on these type of strategies and survey recent results on local strategies for short robot chains and gathering in the continuous time model. We present such strategies for the Robot Chain and the Gathering Problem and analyze them w.r.t. the distance traveled by the robots. For both problems, we survey bounds for the "price of locality", namely the ratio between the cost of our local algorithms and the optimal cost assuming global view, for each individual start con guration.

* Peter Sanders (Karlsruhe Institute of Technology)

Peter Sanders received his PhD in computer science from Universität Karlsruhe, Germany in 1996. After 7 years at the Max-Planck-Institute for Informatics in Saarbrücken he returned to Karlsruhe as a full professor in 2004. He has more than 170 publications, mostly on algorithms for large data sets. This includes parallel algorithms (load balancing,...) memory hierarchies, graph algorithms (route planning, graph partitioning...), randomized algorithms, full text indices,... He is very active in promoting the methodology of algorithm engineering. For example, he currently heads a DFG priority program on AE in Germany. Peter Sanders won a number of prizes, perhaps most notably the DFG Leibniz Award 2012 which amounts to 2.5 million Euros of research money.

Engineering Graph Partitioning Algorithms

The talk will give an overview of our recent work on balanced graph partitioning - partition the nodes of a graph into k blocks such that all blocks have approximately equal size and such that the number of cut edges is small. This problem has numerous applications for example in parallel processing. We report on a scalable parallelization and a number of improvements on the classical multi-level approach which leads to improved partitioning quality. This includes an integration of flow methods, improved local search, several improved coarsening schemes, repeated runs similar to the solutions used in multigrid solver, and an integration into a distributed evolutionary algorithm. Overall this leads to a system that for many common benchmark instances leads to both the best quality solution known and favorable tradoffs between running time and solution quality.