Institut für Theoretische Informatik, Algorithmik
Suche
Institut für Theoretische Informatik, Algorithmik
Institut für Theoretische Informatik, Algorithmik
Institut für Theoretische Informatik, Algorithmik
Lehre
Sommersemester 2009
Seminar: Parametrisierte Algorithmen für NP-schwere Probleme

Parametrisierte Algorithmen für NP-schwere Probleme

Seminar im Sommersemester 2009

Allgemeines

Aktuelles

  • Die Termine für das Seminar stehen fest.

Termine

Datum Zeit Raum Bearbeiter Thema¹
Fr, 08.05.09 11:30 SR 301 Marcus Einführung
Fr, 05.06.09 11:30 SR 301 - Kurzvorträge
Do, 02.07.09 15:45 SR 236 Tobias [10]
Do, 02.07.09 16:30 SR 236 Benjamin [2]
Fr, 03.07.09 11:30 SR 301 Max [4]
Fr, 03.07.09 12:15 SR 301 Oscar [1]
Fr, 17.07.09 11:30 SR 301 Jochen [6]
Fr, 17.07.09 12:15 SR 301 Ben [9]

¹siehe Literatur

Inhalt

Viele relevante und praktisch motivierte Probleme sind NP-schwer und lassen sich daher vermutlich nicht effizient lösen. Für einige NP-schwere Probleme lassen sich jedoch parametrisierte Algorithmen angeben, die eine optimale Lösung in akzeptabler Laufzeit bestimmen können. Die Grundidee parametrisierter Algorithmen besteht darin, die Laufzeit in Abhängigkeit eines Parameters k zu betrachten, der in der Praxis eher klein ist. Die Laufzeit eines solchen Algorithmus ist dann O(f(k)p(n)), wobei f eine berechenbare Funktion, p ein Polynom und n die Eingabegröße bezeichnen. Damit ist die Laufzeit parametrisierter Algorithmen im Wesentlichen polynomiell und die kombinatorische Explosion ist auf einen eher kleinen Parameter beschränkt. Beim Entwurf parametrisierter Algorithmen kommen eine Reihe interessanter Techniken zum Einsatz.

Die Klasse FPT (fixed-parameter tractable) ist die Klasse der Probleme, für die es parametrisierte Algorithmen im obigen Sinne gibt. Aufbauend auf dieser Klasse wird u.a. eine Hierarchie von Komplexitätsklassen W[P] untersucht, von der vermutet wird, dass sie eine eche Hierarchie ist. Analog zur klassischen Komplexitätstheorie kann man im Sinne einer parametrisierten Komplexitätstheorie für einige Probleme beweisen, dass sie unter gewissen Annahmen nicht zur Klasse FPT gehören.

Das Seminar vermittelt einen grundlegenden Überblick über Techniken zum Entwurf parametrisierter Algorithmen sowie über parametrisierte Komplexitätstheorie.

Themengebiete

  • Kernbildung
  • beschränkter Suchbaum
  • Baumzerlegung
  • Color-Coding
  • Iterative Compression
  • Greedy Localization
  • Random Separation
  • Graph Minor Theory
  • Bidimensionality Theory
  • Parametrisierte Komplexitätstheorie
  • Parametrisierte Approximierbarkeit

Voraussetzungen

Voraussetzung für die Teilnahme am Seminar sind Grundkenntnisse aus den Bereichen theoretische Informatik, Algorithmentechnik und Graphentheorie.

Materialien

Literatur

[1] Rolf Niedermeier, Peter Rossmanith, An efficient fixed-parameter algorithm for 3-hitting set, Journal of Discrete Algorithms, Volume 1, Issue 1 (February 2003), pdf
[2] Mike Fellows, Pinar Heggernes, Frances Rosamond, Christian Sloper, Jan Arne Telle, Finding k Disjoint Triangles in an Arbitrary Graph, Parameterized Complexity and Exponential Algorithms, Springer 2005, pdf
[3] J. Chen, Y. Liu, S. Lu, B. O'Sullivan, I. Razgon, A fixed-parameter algorithm for the directed feedback vertex set problem, Annual ACM Symposium on Theory of Computing 2008, pdf
[4] F. Dehne, M. Fellows, F. Rosamond, P. Shaw, Greedy Localization, Iterative Compression, and Modeled Crown Reductions: New FPT Techniques, an Improved Algorithm for Set Splitting, and a Novel 2 k Kernelization for Vertex Cover, pdf
[5] Y. Liu, S. Lu, J. Chen, S. Sze, Greedy Localization and Color-Coding: Improved Matching and Packing Algorithms, Parameterized and Exact Computation, Springer 2006 pdf
[6] Jochen Alber, Hans L. Bodlaender, Henning Fernau, Rolf Niedermeier, Fixed Parameter Algorithms for Planar Dominating Set and Related Problems, Algorithm Theory - SWAT 2000, Springer 2000, pdf
[7] J. Guo, F. Hüffner, R. Niedermeier, A Structural View on Parameterizing Problems: Distance from Triviality, Parameterized and Exact Computation, Springer 2004, pdf
[8] Cai L., Chan S.M., Chan S.O. Random separation: a new method for solving fixed-cardinality optimization problems, Extended abstract in IWPEC 2006, LNCS 4169 (2006) pp. 239–250
[9] Falk Hüffner, Sebastian Wernicke, Thomas Zichner, Algorithm Engineering for Color-Coding with Applications to Signaling Pathway Detection, Algorithmica, Volume 52, Issue 2 (August 2008), pdf
[10] J. Chen, J. Meng, On Parameterized Intractability: Hardness and Completeness, The Computer Journal, vol. 51, no. 1, 2008, pdf
[11] Yijia Chen, Martin Grohe, Magdalena Grüber On Parameterized Approximability, Parameterized and Exact Computation, Springer 2006, pdf

Weiterführende Literatur

[12] J. Flum, M. Grohe, Parameterized Complexity Theory, Springer 2006
[13] R. Niedermeier, Invitation to Fixed-Parameter Algorithms, Oxford 2006
[14] D. Marx, Parameterized Complexity and Approximation Algorithms, The Computer Journal, vol. 51, no. 1, 2008, pdf
[15] J. Gramm, A. Nickelsen, T. Tantau, Fixed-Parameter Algorithms in Phylogenetics, The Computer Journal, vol. 51, no. 1, 2008, pdf
[16] L. Cai, Parameterized Complexity of Cardinality Constrained Optimization Problems,The Computer Journal, vol. 51, no. 1, 2008, pdf
[17] C. Sloper, J. A. Telle, An Overview of Techniques for Designing Parameterized Algorithms,The Computer Journal, vol. 51, no. 1, 2008, pdf
[18] H. L. Bodlaender, A. M. C. A. Koster, Combinatorial Optimization on Graphs of Bounded Treewidth,The Computer Journal, vol. 51, no. 3, 2008, pdf
[19] E. D. Demainem, M. Hajiaghayi, The Bidimensionality Theory and Its Algorithmic Applications,The Computer Journal, vol. 51, no. 3, 2008, pdf
[20] P. Hlineny, S. Oum, D. Seese, G. Gottlob, Width Parameters Beyond Tree-width and their Applications, The Computer Journal, vol. 51, no. 3, 2008, pdf
[21] Faisal N. Abu-Khzam, Kernelization Algorithms for d-Hitting Set Problems, Algorithms and Data Structures, Springer 2007, pdf