Seminar on Parameterized Algorithms and Complexity
| Vuosi | Lukukausi | Päivämäärä | Periodi | Kieli | Vastuuhenkilö |
|---|---|---|---|---|---|
| 2014 | kevät | 17.01-25.04. | 3-4 | Englanti | Mikko Koivisto |
This seminar is cancelled!
Information for international students
The language of the seminar is English.
Yleistä
How to design algorithms for hard problems with running time exponential only in some small parameter of the problem much smaller than the input size? How to show that probably some problems do not admit such algorithms? Design paradigms: treewidth, iterative compression, color coding. Complexity concepts: fixed parameter tractability, W-hierarchy. Problems: Independent Set, Dominating Set, Steiner Tree, and many more...
Prerequisite: The Design and Analysis of Algorithms course or equivalent knowledge. Mature mathematical skills.
Kurssin suorittaminen
Each student will read one or two book chapters or research articles, write a 4 - 6 page summary, and give an oral presentation. In addition, each student will act as an opponent for another presentation.
Reading and writing will take place in Period III. Presentation sessions will be scheduled for Period IV.
Kirjallisuus ja materiaali
A list of articles is currently under construction and will appear here:
From Computer Journal, vol. 51, 2008:
- The Computer Journal Special Issue on Parameterized Complexity: Foreword by the Guest Editors, , and
- Techniques for Practical Fixed-Parameter Algorithms by , , and
- On Parameterized Intractability: Hardness and Completeness by and
- Parameterized Complexity and Approximation Algorithms by
- Parameterized Complexity of Cardinality Constrained Optimization Problems by Leizhen Cai
- An Overview of Techniques for Designing Parameterized Algorithms by Christian Sloper and Jan Arne Telle