Inhalt Advanced algorithmic techniques for solving hard problems: - Linear Programming techniques - theory: Duality, Farkas Lemma, Simplex, Ellipsoid method, etc. - applications (how to use LP): approximation algorithms, fixed-parameter tractable algorithms, Zero_sum Games, etc. - Integer Programming techniques (Problem modelling, Branch and Bound method, Cutting Planes, etc.) - Fixed-parameter (in)tractablity, exponential time algorithms for graph problems: - bounded search trees - dynamic programming on tree decompositions - graph minors (introduction) - color coding - iterative compression, etc. - Iterative methods, heuristics, etc. Zielgruppe This is a course for graduate students (on the PhD and the master level) working in Computer Science or Discrete Mathematics. Voraussetzungen Prerequisite: Höhere Algorithmik.Participants are expected to have good knowledge in (at least one of): discrete mathematics, graph theory, algorithmic geometry, or general algorithms and complexity. The language of the course is English. Literatur Understanding and Using Linear Programming, J. Matou?ek and B. Gärtner, Springer 2006. Introduction to Linear Optimization, Dimitris Bertsimas, John N. Tsitsiklis, Athena Scientific, 1997. Parameterized Complexity Theory, Flum, Grohe, Springer, 2006. Invitation to Fixed-Parameter Algorithms, Niedermeier Oxford University Press, 2006. Schließen