LEA

Summary

Many optimization problems frequently occuring in practise are NP-hard. If P and NP are not the same, then this means that solving these important problem may not be feasible as they require to many resources (time and memory).

One possible approach is to give up on finding an exact solution to the given optimization problem but instead settle for an approximate solution instead. This gives rise to the area of approximation algorithms for NP-hard optimization problems.

In the course of this seminar there will first be an introduction into the area of approximation algorithms and its complexity classes. Then there will be an introduction to general techniques for developing and proving approximation guarantees of algorithms. This is followed by a series of different approximation algorithms for various problems from the area of graph algorithms.

The seminar talks can be presented in German or English, depending on the preference of the students.

List of Topics

  1. Introduction: from NPO to APX
    [Vaz 01] Chapter 1, [ACG+99] Chapter 3.1
  2. Introduction to Linear Programming Techniques for Approximation Algorithms
    [Vaz 01] Chapter 12
  3. Set Cover
    [Vaz 01] Chapter 13-15, [WS 11] Chapter 1.2-1.7
  4. Sparsest Cut
    [Vaz 01] Chapter 21.1-21.5, [WS 11] Chapter 15.1, (15.4)
  5. Applications of Sparsest Cut
    [Vaz 01] Chapter 21.6, [LR 99]
  6. The Multicut Problem
    [Vaz 01] Chapter 18,20, [WS 11] Chapter 8.3
  7. The Multiway Cut Problem
    [Vaz 01] Chapter 19, [WS 11] Chapter 8.1,8.2
  8. Tree embeddings
    [WS 11] Chapter 8.5,8.6
  9. An $O(log n)$-Approximation for Minimum Bisection
    [WS 11] Chapter 15.2,15.3
  10. Graph Partitioning Using Single Commodity Flows
    [KRV 09]
  11. The Steiner Forest Problem
    [Vaz 01] Chapter 22, [WS 11] Chapter 7.4
  12. Steiner Network
    [Vaz 01] Chapter 23, [WS 11] Chapter 11.3
  13. Euclidean TSP
    [Vaz 01] Chapter 11, [WS 11] Chapter 10
  14. Max Cut
    [Vaz 01] Chapter 26 (in particular 26.4), [WS 11] Chapter 6 (in particular 6.2)
  15. Sorting by Reversals
    [BHK 02], [BP 96], [Heu 10], [Chr 98], [KS 95], [Cap 97]

Literatur

  • [ACG+99]
    G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi
    Complexity and Approximation,
    Springer, 1999.
  • [Vaz 01]
    Vijay V. Vazirani,
    Approximation Algorithms,
    Springer 2001
  • [WS 11]
    David P. Williamson and David B. Shmoys,
    The Design of Approximation Algorithms,
    Cambridge University Press 2011
  • [LR 99]
    Tom Leighton and Satish Rao.
    Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms.
    J. ACM 46, 6 (November 1999), 787-832. 1999.
  • [BHK 02]
    Piotr Berman, Sridhar Hannenhalli and Marek Karpinski.
    An 1.375-Approximation Algorithm for Sorting by Reversals.
    In Proceedings of ESA 2002.
  • [BP 96]
    Vineet Bafna and Pavel A. Pevzner.
    Genome Rearrangements and Sorting by Reversals.
    SIAM J. Comput., 25(2), 272-289. 1996.
  • [Heu 10]
    Volker Heun
    Skript zu Vorlesung Algorithmen und Sequenzen,
    2010.
  • [Chr 98]
    David A. Christie.
    A 3/2-approximation algorithm for sorting by reversals.
    In Proceedings of SODA '98, 244-252. 1998.
  • [KRV 09]
    Graph Partitioning Using Single Commodity Flows
    Rohit Khandekar, Satish Rao, Umesh Vazirani JACM 56 (4), pages 385-390. 2009.
  • [KS 95]
    J. Kececioglu and D. Sankoff.
    Exact and Approximation Algorithms for Sorting by Reversals, with Application to Genome Rearrangement.
    Algorithmica, 13 (1-2), 180-210. 1995.
  • [Cap 97]
    Alberto Caprara.
    Sorting by reversals is difficult.
    In Proceedings of RECOMB '97. 75-83. 1997.

Further Links

  • Examples for using the latex classes tikz and beamer. Thanks to Markus Kaiser.

Seminar text

You should write a short text that covers the content of your talk. This document should make it possible for the reader to understand what you did in your talk and it should serve as an entry point if one whishes to obtain further detail about the topic. This means that you, in particular, you could have material in there that you did not cover in your talk, but it also means that you need to have a comprehensive list of references that makes it easy to dig up the sources (please also include the original sources and not just the references to the book).

The text should cover approximately 7 ± 1 page(s), where table of contents, list of references, and pictures do not count (this means if you run out of space you can draw a picture :)). A latex-template is available here.

The deadline for handing in this text is July, 11, 2014.