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.30-13.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, self-stabilization, rollback recovery, distributed transactions, blockchains, and quantum cryptography. Participants will receive a free copy of the textbook (subject to availability).

TUESDAY 22 January Neil Yorke-Smith (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 sub-solving 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 hands-on 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 Yorke-Smith is an Associate Professor of Socio-Technical 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 socio-technical situations, with a particular current interest in agent-based methodologies and behavioural factors in automated planning and scheduling. Information and publications: http://member.acm.org/~nyorke-smith

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 model-based 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 well-known k-OPT heuristic and concerning Euclidean TSP. This also brings us into contact with the concepts of fine-grained 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 NP-complete 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 NP-hard? 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 so-called 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 game-specific circumstances. Hearn and Demaine translate this logic into different games, ranging from zero-player games like Conway’s Life, via puzzles (being one-player games) such as Sokoban and Rush Hour (with sliding blocks), to two-player games like Amazons. And how about team games? Crucial is the construction of so-called gadgets. For each game, simulation of and- and or-gates 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 self-contained, and include assignments that deal with puzzles and reductions. See the web for the so-called plank puzzle.

References:
[1] R.A. Hearn and E.D. Demaine, Games, Puzzles & Computation, AK Peters, 2009.
[2] A.N. Siegel, Combinatorial Game Theory, AMS, 2013

Programme:
1. Intro: Games and complexity classes, constraint logic
2. Gadgets, planarity, exercises
3. Tip-Over is NP-complete
4. Rush Hour is PSPACE complete, plank puzzle
5. Combinatorial game theory
6. Wrap-up: other classes of games

Social

On one of the days (to be determined), the course will be followed by IPA-sponsored 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 IPA-members 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.