NP-Schwere Probleme treten in unserem Alltag und vorallem im Alltag eines Informatikers häufig auf. Zwei prominente Vertreter sind das Traveling-Salesman-Problem und das Cliquen-Problem. Wobei letzteres zum Beispiel in der Analyse von (sozialen) Netzwerken eine große Rolle spielt.
Obwohl es bis heute noch keinen polynomiellen Algorithmus zur Lösung NP-vollständiger Probleme gibt, heißt dies nicht, das alle NP-vollständigen Probleme aus algorithmischer Sicht nicht fassbar wären.
Über die Jahre haben sich drei besonders erwähnenswerte Ansätze herauskristallisiert um viele NP-schwere Probleme algorithmisch zu bändigen. In diesem Seminar wollen wir uns mit approximativen, randomisierten und parametrisierten Algorithmen zur Lösung bzw. Annäherung an die Lösung von NP-vollständigen Problemen beschäftigen. Inhärent dazu gehören auch untere Schranken für die Komplexität der Probleme.
| Einfürung in Aproximative und Parametrisierte Algorithmen mit dem Vertex-Cover-Problem | Tobias Lieber | Betreuer: | |
| Approximative Algorithmen für TSP | Julian Asamer | Riko Jacob | 12.1.2011 10 - 12 Uhr |
| Approximative Algorithmen für TSP auf planaren Graphen | Markus Englert | Tobias Lieber | 12.1.2011 10 - 12 Uhr |
| PTAS, FPTAS: Sehr gut lösbare Probleme wie BinPacking und Knapsack | Jochen Günther | Riko Jacob | ---- |
| Nicht-handhabbare Probleme: Untere Schranken mittels PCP | Julian Brunner | Tobias Lieber | 14.1.2011 11 - 13 Uhr |
| Parametrisierte Komplexität: Treewidth-basierte Verfahren z.B. Clique | Andreas Schropp | Tobias Lieber | 19.1.2011 10 - 12 Uhr |
| Parametrisierte Komplexität: Kernelbasierte Verfahren | Christoph Flake | Tobias Lieber | 19.1.2011 10 - 12 Uhr |
| (syntaktisch definierte) Klassen der Approximierbarkeit | | | |
| Nicht-handhabbare Probleme in der parametrisierten Komplexität | | | |
| Eine Untere Schranke für das Cliquen-Problem via Graph-Produkt | Safak Ökmen | Riko Jacob | ???? |
| Randomized Rounding | Leonard Höss | Riko Jacob | 21.1.2011 12 - 13 Uhr |
| Approximative Algorithmen für Dense-k-Subgraph | Anton Wilhelm | Tobias Lieber | 26.1.2011 10 - 12 Uhr |
| Sorting by Reversal | Galina Volynets | Jeremias Weihmann | 26.1.2011 10 - 12 Uhr |
| Beispielprobleme aus dem Scheduling | | | |
Anmeldung
Es gibt noch unbesetzte Themen.
Falls Sie Interesse an dem Seminar haben setzen Sie sich mit
Tobias Lieber in Verbindung.
Die Vorbesprechung fand am Donnerstag, 15.07.2010 um 14:00 im Raum
MI 03.11.018 statt.
Alle Vorträge finden im Raum MI 03.11.018 statt.
Hinweise
Jeder Teilnehmer wählt ein Thema und sieht sich nach passender Literatur um.
Gibt es Fragen zur Beschaffung der Literatur oder zum Einstieg in das Thema so helfen wir gerne.
Die Aufgabe besteht darin,
- passende Literatur zu finden, zu lesen und zu verstehen,
- einen sauberen Vortrag über das Thema zu erstellen und zu halten, und
- eine kurze Ausarbeitung über das Thema zu schreiben.
Eine Vorlage für die Ausarbeitung findet sich in
diesem Ordner.
