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
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
- Introduction: from NPO to APX
[Vaz 01] Chapter 1, [ACG+99] Chapter 3.1
- Introduction to Linear Programming Techniques for Approximation
[Vaz 01] Chapter 12
- Set Cover
[Vaz 01] Chapter 13-15, [WS 11] Chapter 1.2-1.7
- Sparsest Cut
[Vaz 01] Chapter 21.1-21.5, [WS 11] Chapter 15.1, (15.4)
- Applications of Sparsest Cut
[Vaz 01] Chapter 21.6, [LR 99]
- The Multicut Problem
[Vaz 01] Chapter 18,20, [WS 11] Chapter 8.3
- The Multiway Cut Problem
[Vaz 01] Chapter 19, [WS 11] Chapter 8.1,8.2
- Tree embeddings
[WS 11] Chapter 8.5,8.6
- An $O(log n)$-Approximation for Minimum Bisection
[WS 11] Chapter 15.2,15.3
- Graph Partitioning Using Single Commodity Flows
- The Steiner Forest Problem
[Vaz 01] Chapter 22, [WS 11] Chapter 7.4
- Steiner Network
[Vaz 01] Chapter 23, [WS 11] Chapter 11.3
- Euclidean TSP
[Vaz 01] Chapter 11, [WS 11] Chapter 10
- Max Cut
[Vaz 01] Chapter 26 (in particular 26.4), [WS 11]
Chapter 6 (in particular 6.2)
- Sorting by Reversals
[BHK 02], [BP 96], [Heu 10], [Chr 98], [KS 95], [Cap 97]
G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi
Complexity and Approximation,
- [Vaz 01]
Vijay V. Vazirani,
- [WS 11]
David P. Williamson and David B. Shmoys,
The Design of
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]
Skript zu Vorlesung Algorithmen und Sequenzen,
- [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]
Sorting by reversals is difficult.
In Proceedings of RECOMB '97. 75-83. 1997.
- Examples for using the latex classes tikz and
beamer. Thanks to Markus Kaiser.
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
The deadline for handing in this text is July, 11, 2014.