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

Magnús Már Halldórsson

School of Computer Science
Reykjavík University
Iceland

Approximation Algorithms for NP-Hard Combinatorial Problems

Abstract

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

• M. M. Halldórsson. Approximation algorithms for NP-hard combinatorial problems. EWSCS 2013 course slides.
  • Lecture 1: intro, problems, approaches, naive approximations [ppt]
  • Lecture 2: local search, greedy algorithms [ppt], partitioning [pdf] (+ notes on it [pdf])
  • Lecture 3: probabilistic method [ppt], LP rounding [ppt], exercises to lecture 3 [html]
  • Lecture 4: semidefinite programming [ppt], applications to wireless computing [ppt]
• Videos from the lectures.
  • Lecture 1 [mp4]
  • Lecture 2 [mp4]
  • Lecture 3 [mp4]
  • Lecture 4 [mp4]
• R. B. Boppana, M, M. Halldórsson. Approximating maximum independent sets by excluding subgraphs. BIT, v. 32, n. 2, pp. 180-196, 1992.
• M. M. Halldórsson, J. Radhakrishnan. Greed is good: approximating independent sets in sparse and bounded-degree graphs. Algorithmica, v. 18, n. 1, pp. 145-163, 1997. [doi link]
• U. Feige, M. M. Halldórsson, G. Kortsarz, A. Srinivasan. Approximating the domatic number. SIAM J. of Comput., v. 32, n. 1, pp. 172-195, 2002. [doi link]
• R. Bar-Yehuda, K. Bendel, A. Freund, D. Rawitz. The local ratio technique and its application to scheduling and resource allocation problems. In M. C. Golumbic, I. B.-A. Hartman, eds., Graph Theory, Combinatorics and Algorithms, v. 34 of Operations Research/Computer Science Interface Series, pp. 107-143. Springer, 2005. [doi link]
• R. Bar-Yehuda, M. M. Halldórsson, J. Naor, H. Shachnai, I. Shapira. Scheduling split intervals. SIAM J. of Comput., v. 36, n. 1, pp. 1-15, 2006. [doi link]
• Y. Ye, A. Borodin. Elimination graphs. ACM Trans. on Algorithms, 2012. [doi link]

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