Course: Algorithms and Complexity
Eindhoven University of Technology, Eindhoven
January 21 – 25, 2019
IPA organises Advanced Courses on each of its major research fields: Algorithmics and Complexity, Formal Methods and Software Technology. Each of these Advanced Courses intends to give an overview of (part of) the research of IPA in this specific field.
This Advanced Course, which is hosted by IPA at the Eindhoven University of Technology, focusses on subject areas in algorithmics and complexity where successful research is being conducted by groups in IPA, with some prominent international speakers as well. From several of these areas, topics are taken and treated in a course day each. Course components consist of lectures mixed with active training (exercises, assignments, etc.).
Dates, Location and Programme
The lectures will take place in lecture room MF 13 (also known as room MF5.209) on floor 5 of building Metaforum at the TU/e campus. The overall schedule of the course is as follows: course days will start at 10.00 and last until approximately 16.30 hours. Short coffee breaks are planned at around 11.00 and around 14.45 and an organised lunch break at, roughly, 12.3013.30.
MONDAY 21 January  Wan Fokkink (VU) 
Distributed Algorithms A wide range of distributed algorithms will be discussed, based on the textbook Wan Fokkink, Distributed Algorithms: An Intuitive Approach (2nd edition), MIT Press, 2018 Topics include snapshots, termination detection, consensus, selfstabilization, rollback recovery, distributed transactions, blockchains, and quantum cryptography. Participants will receive a free copy of the textbook (subject to availability). 

TUESDAY 22 January  Neil YorkeSmith (TUD) 
Constraint Programming
How do we solve combinatorial optimisation problems? Constraint Programming (CP) is a capable and flexible approach that separates problem modelling from model solving. With CP, we model problems by declaring variables, objective functions, and constraints. For example Linear Programming (LP) is a special case of CP restricted to linear constraints. With CP, we solve the model by using generic solving algorithms that combine powerful inference with systematic search. The inference uses constraint propagation, a logical consistency technique, and global constraints, which encapsulate specialised subsolving algorithms. The search can be complete or incomplete, and we can combine CP search with other methods, such as LP relaxations.This tutorial offers a handson introduction to Constraint Programming. We will learn best practice in building CP models and see how CP solvers operate. We will try a range of examples using the open source CP modelling language MiniZinc and its interfaces to several solvers.Presenter
Neil YorkeSmith is an Associate Professor of SocioTechnical Algorithmics in the Faculty of Electrical Engineering, Mathematics and Computer Science at the Delft University of Technology (TU Delft). His research focuses on intelligent decision making in complex sociotechnical situations, with a particular current interest in agentbased methodologies and behavioural factors in automated planning and scheduling. Information and publications: http://member.acm.org/~nyorkesmith 

WEDNESDAY 23 January  Mark de Berg (TU/e) and Kevin Buchin (TU/e) 
Traveling Salesmen and Migrating Birds: Algorithms for Planning and Analyzing Routes
People, goods, animals: everything moves. Hence, optimizing and analyzing movements is important in many settings. This leads to a host of challenging algorithmic questions, often involving spatial data. Today we will give some examples of such questions and of the techniques that have been developed within computational geometry to solve them.In the morning lectures we discuss algorithms for analyzing trajectory data, like GPS data from vehicles or animals. We focus on algorithms for two common analysis tasks: segmentation and clustering. Segmentation asks to split and possibly group trajectories such that they have similar movement characteristics. Clustering asks to group similar trajectories or subtrajectories. We present geometric and modelbased approaches to segmentation, and algorithms for clustering based on geometric similarity measures.
In the afternoon lectures we then turn our attention to algorithms for route planning, and in particular to the Traveling Salesman Problem (TSP), one of the most famous problems in all of computer. We will discuss some recent algorithmic results on TSP, concerning the wellknown kOPT heuristic and concerning Euclidean TSP. This also brings us into contact with the concepts of finegrained complexity and conditional lower bounds, which form one of the exciting developments in algorithms research in the past few years. 

THURSDAY 24 January  Hans Bodlaender (UU) 
Parameterized algorithms and complexity
In the field of parameterized algorithms and complexity, we look at problems with one additional assumption: one parameter of the input is small.Different problems give a different algorithmic complexity: the problem to decide if we can color a graph with k colors remains NPcomplete when k=3. If we want to decide if there is an independent set with k vertices in a given graph, then this can be solved trivially in O(n^k) time, and to decide if exists a vertex cover with k vertices in a given graph, then this has an O(2^k n) algorithm. The field of parameterized algorithms distinguishes between a behavior like independent set (polynomial, but the polynomial grows with the parameter; captured by the class XP), and like vertex cover (polynomial, with a running time that is the product of a function of the parameter and a fixed polynomial: such problems are said to be fixed parameter tractable, or in FPT.)In the lectures, we discuss the different notions, algorithmic techniques to obtain FPT algorithms, and hardness proofs. The techniques include the notion of kernelization (with applications to preprocessing), and the notion of treewidth. 

FRIDAY 25 January  Walter Kosters and Hendrik Jan Hoogeboom (UL) 
Game Complexity
Games come in many flavours. They can be easy, they can be hard: though the rules of Go are simple, the game is very complex. But how hard is such a game from the viewpoint of computational complexity theory? Can we generalize to arbitrary board sizes? Is it NPhard? Is it in PSPACE? And what are corresponding decision problems anyhow?
Bob Hearn and Erik Demaine have written a book [1] that tries to provide a uniform view on game complexity. They start from special types of graphs, building socalled Contraint Logic, for which several variants are closely tied to specific complexity classes. A typical decision problem, or winning condition, might be the question whether a given edge in the graph can be finally reversed by a series of edge reversals, where an edge reversal is allowed in gamespecific circumstances. Hearn and Demaine translate this logic into different games, ranging from zeroplayer games like Conway’s Life, via puzzles (being oneplayer games) such as Sokoban and Rush Hour (with sliding blocks), to twoplayer games like Amazons. And how about team games? Crucial is the construction of socalled gadgets. For each game, simulation of and and orgates within the specific game rules is the basis of the translation, usually referred to as reduction. As a special topic we will also address Combinatorial game theory [2]: how can you assign values to games, how can you add these numbers, and are they really numbers? Examples include the games Hackenbush and Nim. The lectures are essentially selfcontained, and include assignments that deal with puzzles and reductions. See the web for the socalled plank puzzle. References: Programme: 
Social
On one of the days (to be determined), the course will be followed by IPAsponsored drinks and snacks; details to be announced.
Registration
Follow this link to register for this IPA course. Registration will close Friday January 11th at noon (CET).
Accommodation for IPA PhD students
Unlike for IPA’s Fall Days, overnight accommodation is not included by default for this course. The schedule is set up in such a way that it is feasible for many students to commute. In the event this is not feasible—e.g. for students from Groningen and Twente—please let us know and we will provide basic overnight accommodation. You can specify your accommodation needs on the registration form.
Costs
The courses are intended for IPA PhD students, giving them an overview of IPA’s research. For IPA PhD students, participation is free of charge (including overnight accommodation if desired, see below), but registration is required. Other IPAmembers can attend if there is capacity left, and the same holds for PhD student and other members of associated research schools. For these categories we may charge costs for the course material, lunches, etc, and IPA will not provide overnight accommodation. Contact us for information regarding pricing. For all categories, in case of no show extra charges may apply.