Mini-courses

 

1. Marcin Bieńkowski (Wroclaw University): Introduction to Online Algorithms

Many real-life applications, ranging from caching and scheduling to navigation and currency trading, require online solutions. Online algorithms learn the input sequence gradually and have to produce parts of the output immediately, without the knowledge about future demands or requests. In theoretical computer science, the performance of such solutions is measured by comparing their cost to the cost of an optimal solution (which knows the whole input in advance). This type of competitive analysis became the prevalent yardstick used by the TCS community and also gained acceptance in some applied areas. 

In this mini-course, we will cover some generic approaches of tackling online problems, such as potential functions, doubling method, primal-dual schemes, online randomized rounding, classify and select, and work functions. The course will be focused on these techniques and their application to various online problems. No prior knowledge about the competitive analysis is assumed.

 

2. Darek Dereniowski (Gdańsk University of Technology): Algorithms for Graph Searching Problems

The graph searching problems became an intensive field of study and many searching models have been developed over the years. In a very wide perspective, we see graph searching problems as ones in which the goal is to design an algorithm (often called a search strategy) that, when executed for a given input graph, should provide a set of actions/moves that will guarantee that a hidden target in the graph is localized. Under which conditions the algorithm announces a success and what are the valid actions it may take depends on a selected searching model. In this mini-course we will focus on few of them, selecting ones that exhibit interesting algorithmic techniques and are important from the graph-theoretic point of view. By the latter we refer to the fact that several searching problems proved to be equivalent to some graph parameters, like pathwidth, treewidth, cutwidth, bandwidth, to mention just a few.

The lecture will cover three aspects of our subject: basic properties and ties to graph theory, selected algorithms and the role of information in the graph searching games. The first aspect will include the relations to graph parameters mentioned above. The aim of the second part is to study some algorithmic ideas that proved to be useful in this field, while in the last part we will see how the dynamics of the searching games change in absence of complete information about the input, thus we will make a shift towards online and distributed algorithms.

 

3. Adrian Kosowski (IRIF/Inria Paris): Compact and Distributed Graph Data Structures

This course addresses the issue of designing compact data structures for retrieving information in response to queries about graph data. Many of the queries we consider are related to efficient navigation in a graph, e.g.: “Given nodes s and t, what is the distance between s and t?” or “How to route a data packet from its current location in the network towards its destination t?” Processing such queries efficiently often requires not only that information be retrieved from the data structure quickly, but also that it is available locally, so that, e.g., a navigational decision can be taken at a network node without consulting external resources. In this setting, we will look at the interplay between several parameters of compact data structures and the algorithmic schemes which operate on them, including: the time required to process a query, the space requirements of the data structure, the time required to encode the data structure, and the cost of organizing data in a distributed manner as opposed to implementing a centralized solution.

The lectures will feature the following topics:

(i) Compact data structures and labeling schemes on graphs: adjacency labeling, distance labeling, labelings for nearest common ancestor queries in trees, maximum flow queries, and related problems.

(ii) Distance labeling and shortest path queries in (almost) planar graphs: distance queries in graphs with small separators, the notion of path separators, graphs with small highway dimension, contraction hierarchies, shortest-path queries in real-world road networks.

(iii) Compact routing in networks: trade-offs between routing table size and stretch, name dependent and name independent routing schemes in trees and arbitrary graphs.

 

4. Łukasz Kowalik (Warsaw University): Introduction to Parametrized Algorithms

Parameterized complexity is one of the most successful approaches to NP-complete problems. It tries to capture in a rigorous way the phenomenon observed in practice that for many NP-complete problems the instances are not equally hard. The goal is to identify hardness measures (called parameters) which determine the hardness and to get algorithms which perform provably fast on instances with low parameter value.

In this mini-course we present the very basics of parameterized algorithms. We focus mostly on graph problems. We will start from simple branching algorithms for vertex cover and the classic color-coding algorithm for finding paths of length k. Then we introduce the concept of kernelization and illustrate it with a few examples. A large fragment of the course is devoted to the notions of pathwidth and treewidth and designing algorithms that perform dynamic programming over tree decomposition. The course will conclude with an example of so-called algebraic approach in parameterized algorithms, by presenting the fastest known algorithm for finding paths of length k in directed graphs.

Exercises will include, among others, branching algorithms, kernelization and dynamic programming over tree decompositions.

 

5. Bartek Sawik (AGH Krakow): Linear and Mixed Programming

This mini-course will consist of three parts. The first part includes introduction to combinatorial, linear and mixed integer programming models. Basic terminology of the optimization models will be presented, for example: objective function, decision variables, input parameters, approximation, optimal solution, gap, CPU, Simplex method for linear programming, Branch-and-Bound method for integer and mixed integer programming.

In the second part selected models of combinatorial optimization and mixed integer programming are going to be explained. Problems with indivisibilities: integer programs for knapsack, bin packing and cutting stock problems. Linear programming formulation for transportation problem will be described. Mixed integer programs for assignment, traveling salesman problems (TSP) are explained. This include the difference between asymmetric vs. symmetric TSP and Vehicle routing problems.

The last part comprises definition of multi-objective optimization with explanation of weighted-sum, lexicographic and reference point approaches. Some practical examples of multi-criteria optimization problems are provided, such as: portfolio optimization for investments, assignment problems for hospital and Green Vehicle Routing problems for supermarket chain transportation.