Seminar: Approximation Algorithms
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
- Introduction: from NPO to APX
[Vaz 01] Chapter 1, [ACG+99] Chapter 3.1
- Introduction to Linear Programming Techniques for Approximation
Algorithms
[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
[KRV 09]
- 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]
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.
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 10 ± 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, 15, 2018.
July 2022: Jens Quedenfeld completed his doctoral degree.
June 2022: Maximilian Janke completed his doctoral degree.
March 2022: Alexander Eckl completed his doctoral degree.
June 2021: Leon Ladwig completed his doctoral degree.
February 2020: The Program Committee of SWAT 2020 is chaired by Susanne Albers.
February 2020: Susanne Albers is invited speaker at the ACM India Annual Event.
ESA/ALGO 2019 will be organized by Susanne Albers and her group.
May 2019: Susanne Albers is invited speaker at the symposium 50 Years Informatics
July 2019: Susanne Albers is invited speaker at SIROCCO 2019, Italy.
December 2017: Susanne Albers will give keynote address at the
Graduation Day, Department of Computer Science at RWTH Aachen University.
April 2017: New Research Training Center AdONE, funded by the German Research Foundation.
Susanne Albers receives ERC Advanced Grant. Press release of the Bavarian State Ministry of the Sciences, Research and the Arts.
August 2016: Susanne Albers is keynote speaker at Euro-Par 2016,
Grenoble.
Susanne Albers, Nicole Megow and Andreas S. Schulz will organize MAPSP 2017.
Juni 2016: Susanne Albers gives an invited lecture at the Academy of Sciences and
Literature, Mainz.
September 2015: Susanne Albers is invited speaker at
MPI-INF – 25th Anniversary.
The program features several Turing Award winners,
Leibniz Prize winners, Humboldt Prize winners and ERC Grant winners.
June 2015: Susanne Albers is keynote speaker at the 31st International Symposium on Computational Geometry (SOCG15), Eindhoven.
June 2015: Susanne Albers is invited speaker of the tutorial on Network Creation Games: How Does the Internet Form?
organized by Erik D. Demaine (MIT) and MohammadTaghi Hajiaghayi (University of Maryland).
16th Conference on Electronic Commerce (EC15), Portland, Oregon.
