Course: Algorithms and Complexity

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).

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

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.

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.

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