## Topic outline

• ### Approximation Algorithms

Description

The task of determining an optimal solution for a given problem (discrete optimization problem) is ubiquitous in computer science. A prominent example is the Travelling Salesman Problem where the goal is to find a shortest tour that visits a given set of locations. Unfortunately, for many optimization problems, no efficient algorithms are known (and under standard complexity theoretic assumptions, no such algorithms are expected to exist). However, feasible solutions are still required in practice. Thus, one approach is to determine efficient algorithms that provide provably good (but not necessarily optimal) solutions.

In this lecture we discuss the design and analysis of techniques for such algorithms. Namely, we consider methods that provide a guaranteed approximation ratio (i.e., a bounded ratio between the objective value of a computed solution and the objective value of an optimal solution). For example, we will see an algorithm for the Travelling Salesman Problem where the ratio between the tour provided by the algorithm is at most two times the value of a shortest tour.

Learning Objectives

By the end of this course participants should be able to analyze simple approximation algorithms with respect to their quality. They should also be able to apply basic design techniques (e.g., greedy, local search, scaling, and LP-based methods) to approximately solve discrete optimization problems.

Lecturer: Dr. Joachim Spoerhase (joachim.spoerhase@aalto.fi)

Teaching Assistant: Wanchote Jiamjitrak (wanchote.jiamjitrak@aalto.fi)

There will be weekly exercise sheets (10 in total and with 20 points each, that is, 200 points in total). At the end of the course (May, 21) there will be an oral exam (with at most 200 points credited). For passing the course is a necessary requirement to achieve 35% of the exercise points and 35% of the points in the oral exam. The overall grade will be determined by the exercise points and by the oral exam (50% each).

Below we give a tentative grade scale (the limits may be lowered later)

grade 5: 80% of the points

grade 4: 68% of the points

grade 3: 57% of the points

grade 2: 46% of the points

grade 1: 35% of the points

Prerequisites

Knowledge of basic algorithms and algorithmic techniques, understanding and writing mathematical proofs, big-Oh notation, ideally basics of graph theory

Tentative List of Topics

1. Introduction - Vertex Cover
2. Set Cover, Shortest Superstring, Reductions
3. Steinertree and Multiway-Cut
4. Linear Programming (LP)
5. LP-Based Approaches for Set Cover
6. k-Center via Parametric Pruning
7. Min-Degree Spanning Trees via Local Search
8. FPTAS for Knapsack
9. PTAS for Euclidean TSP
10. Scheduling Jobs on Parallel Machines via LP-Rounding
11. Maximum Satisfiability via Randomized LP-Rounding