Semester | Summer 2017 [ Other terms: · Sommer 15 · Sommer 12 · Sommer 09 ] |

Module # | INF-ALG-14 |

Event # | INF-ALG-015 , INF-ALG-016 |

Programmes | Master Informatik, Master Informations-Systemtechnik, Master Wirtschaftsinformatik |

IBR Group(s) | ALG (Prof. Fekete) |

Type | Vorlesung/Übung |

Lecturer | |

Assistant | |

Credits | 5 |

Hours | 2+1+1 |

Time & Place | Lecture: Tuesday 15:00-16:30 PK3.3 Lecture: 11.04.2017, Exercises: TBA, small Tutorial: TBA Prerequisites are knowledge of algorithms and data structures, basic graph problems and graph algorithms (e.g., as provided in the lecture "Netzwerkalgorithmen"); basic knowledge from theoretic computer science (NP-completeness) are helpful, but will definitely be supplemented. Many interesting and natural algorithmic problems (e.g., the Traveling Salesman Problem) are NP-complete - hence, we cannot expect to find a "perfect" algorithm that (i) always and (ii) fast finds (iii) an optimal solution. However, hard problems still need to be solved! In this class we consider algorithms that do not necessarily find an optimal solution, but that (i) always and (ii) fast find a (iii) provably good solution. Among the topics of this class are: - A basic introduction to NP-completeness and approximation
- Approximation for vertex and set cover
- Packing problems
- Tour problems and variations
- Current research problems
## Announcements and Dates~~The second tutorial will be be May, 10th in IZ358. This will be the regular slot from now on.~~~~The first tutorial will be April, 25th in the regular lecture slot, i.e., there is a tutorial instead of a lecture this week.~~~~The lecture starts in the second week of the semester, i.e., the first appointment is 11.04.2017 15:00-16:30 in PK3.3.~~~~If you missed the first lecture, you can still join! If you have any question, simply write a mail to Dominik Krupke. We are happy about every interested student.~~~~Since a large percentage of the students has problems with the slots for exercises and small tutorials, these will be moved to a more convenient slot. You will soon receive an e-mail regarding this matter.~~
## General Information- We do only use this website and the below mentioned mailinglist to distribute informations. No studip etc.
- If there are any questions, do not hesitate to write a mail to Dominik Krupke.
## Homework SetsThere will be biweekly mandatory homework. Please check the material area.## Literature:The first part of the lecture will be on basic results for which the following books can be useful- Vazirani, Vijay V.: Approximation Algorithms, Springer-Verlag, 2001.
- Approximation Algorithms for NP-hard problems edited by Dorit S. Hochbaum, more info.
- The Design of Approximation Algorithms by David P. Williamson and David B. Shmoys, published by Cambridge University Press. more info
## Mailing List There will be a You may also want to check out the alg-studs mailing list which is similiar to cs-studs but for algorithmic students. ## MaterialIn the password protected material area you can find the video recordings of the lecture and further material as the slides of the tutorials. The password will be announced in the first lecture. |