Algorithmic Workshop

day 1, October 10th (Friday), room 0174
Jarosław Byrka, LP-based algorithms for Facility Location problems

9.00-10.30 - lecture: LP rounding algorithms for Facility Location
10.30-12.00 - exercises
12:00-13:00 - lunch break
13.00-14.30 - lecture: Primal dual algorithms for UFL
14.30-16.00 - exercises
16.00 - solutions


In facility location the task is to select a subset of possible locations to open facilities and to connect clients to opened facilities. The goal is to minimize the total cost of opening facilities and connecting clients.
Facility Location has been the study case for approximation algorithms for decades. We will use this setting to introduce a number of LP-based algorithmic techniques. In particular we will see an LP-rounding algorithm, a Primal-Dual algorithm, and an analysis of an algorithm using a so-called factor-revealing LP. If time allows, we will also briefly discuss recent algorithms for the k-median problem.

day 2, October 11th (Saturday), room 0174
Ola Svensson, Approximation Algorithms for the Traveling Salesman Problem

9.00-10.30 - lecture
10.30-12.00 - exercises
13.00-14.30 - lecture
14.30-16.00 - exercises
16.00 - solutions


One of the most classic optimization problems is the traveling salesman problem. In these lectures, we will first explain and analyze the classic approaches for the symmetric version as well as the asymmetric version. We then present the students to the newest results and point out interesting future directions, i.e., open problems.
In particular, we will cover the following recent results:

• The tight result that any 2-edge-connected subcubic graph has a tour of length 4n/3-2/3.
• The best known O(log n/loglog n)-approximation algorithm for the asymmetric traveling salesman problem.

day 3, October 12th (Sunday), room 0174
Dariusz Kowalski, Algorithmic aspects of communication channel (selected topics)

9.00-10.00 - lecture: Foundations of communication on multiple-access channel
10.00-11.45 - exercises and open problems
11.45-12.30 - solutions
12.30-13.30 - lunch break
13.30-14.30 - lecture: Dynamic aspects of multiple-access channel
14.30-16.00 - exercises and open problems
16.00-16.30 - solutions
16.30-17.00 - lecture: Shared memory and other extensions + open problems


In this tutorial we focus on algorithms and limitations for communication and computation problems on communication channel. We will address selected topics - both classical and modern, mainly from perspective of distributed algorithms, i.e., algorithms run autonomously by many channel users. The topics include (not necessarily disjoint):

• channel with errors, e.g., what throughput/stability/latency can be achieved on a channel in the presence of errors (random, adversarial)
• channel with contention, e.g., what throughput/stability/latency can be achieved on a channel with some limits on amount of successfully transferred data
• dynamic processes on a channel, e.g., what throughput/stability/latency can be achieved on a channel if data and channel conditions are dynamic