18th Estonian Winter School in Computer Science (EWSCS)
XVIII Eesti Arvutiteaduse Talvekool

Palmse, Estonia, March 3 - 8, 2013

Magnús Már Halldórsson

School of Computer Science
Reykjavík University

Approximation Algorithms for NP-Hard Combinatorial Problems


The great majority of optimization problems are NP-hard, and are therefore unlikely to be solvable efficiently. One of the major ways of dealing with intractability is to seek efficient algorithms that find good but non-optimal solutions. The area of approximation algorithms deals with designing and analysing algorithms that provable performance guarantees.

The objective of this module is to introduce the audience to the main strategies for designing approximation algorithms and the core techniques for analyzing them. The strategies covered include greedy algorithms, local search, subgraph removal, the probabilistic method, local ratio, LP rounding, and semi-definite programming. We consider them in the context of classical graph problems, such as Vertex Cover, Maximum Independent Set, Graph Coloring, Minimum Dominating Set and Domatic Partition.

The only background assumed is a familiarity with algorithms at the BSc level, and a degree of mathematical maturity.

Course materials

Valid CSS! Valid XHTML 1.0 Strict Last changed April 17, 2016 21:04 EET by local organizers, ewscs13(at)cs.ioc.ee
EWSCS'13 page: http://cs.ioc.ee/ewscs/2013/