
day 1, October 10th (Friday), room 0174
JarosÅ‚aw Byrka, LPbased algorithms for Facility Location problems 9.0010.30  lecture: LP rounding algorithms for Facility Location 10.3012.00  exercises 12:0013:00  lunch break 13.0014.30  lecture: Primal dual algorithms for UFL 14.3016.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 LPbased algorithmic techniques. In particular we will see an LProunding algorithm, a PrimalDual algorithm, and an analysis of an algorithm using a socalled factorrevealing LP. If time allows, we will also briefly discuss recent algorithms for the kmedian problem. day 2, October 11th (Saturday), room 0174 Ola Svensson, Approximation Algorithms for the Traveling Salesman Problem 9.0010.30  lecture 10.3012.00  exercises 13.0014.30  lecture 14.3016.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:
day 3, October 12th (Sunday), room 0174 Dariusz Kowalski, Algorithmic aspects of communication channel (selected topics) 9.0010.00  lecture: Foundations of communication on multipleaccess channel 10.0011.45  exercises and open problems 11.4512.30  solutions 12.3013.30  lunch break 13.3014.30  lecture: Dynamic aspects of multipleaccess channel 14.3016.00  exercises and open problems 16.0016.30  solutions 16.3017.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):
