Approximationsalgorithmen
| Inhalt: |
| Verschiedene wichtige und in der Praxis häufig auftretende Optimierungsprobleme lassen sich nicht in Polynomialzeit lösen (bei P ungleich NP), eine exakte Lösung erfordert somit sehr großen Zeitaufwand. Daher versucht man häufig Näherungslösungen zu erzielen, die man effizient, d.h. in Polynomialzeit, finden kann. Von Interesse ist dann natürlich, welche Qualität der erhaltenen Lösung man garantieren kann. Vorgestellt und analysiert werden algorithmische Approximationsverfahren für verschiedene typische Probleme, an denen man gut geeignete Lösungstechniken erlernen kann. Die in der Vorlesung vorgestellten Techniken werden in den zugehörigen Übungen angewandt und vertieft. |
| Literatur: |
|
| Teilnehmer: |
| Studierende der Informatik, Mathematik und ggf. weiterer Fachrichtungen |
| Abschluss: |
| mündliche Prüfung |
| Übungen: |
