On Some Approximation Algorithms of Magnús Halldórsson

Abstrakt:

Several approximation algorithms will be presented. A common theme for these algorithms is that they were either designed by Magnús Halldórsson (perhaps with coauthors), or are based on ideas that appeared in work of Magnús. Another common theme is that the algorithms have clever but simple proofs of correctness. Among the algorithms presented will be a recent algorithm with the current best approximation ratio for finding a maximum clique in a graph.