Parameterized Approximation Algorithms
| Thesis title in Czech: | Parameterized Approximation Algorithms |
|---|---|
| Thesis title in English: | Parameterized Approximation Algorithms |
| English key words: | fixed-parameter tractability|approximation|algorithms|graphs |
| Academic year of topic announcement: | 2021/2022 |
| Thesis type: | dissertation |
| Thesis language: | |
| Department: | Department of Applied Mathematics (32-KAM) |
| Supervisor: | Mgr. Martin Koutecký, Ph.D. |
| Author: | Mgr. Tung Anh Vu - assigned and confirmed by the Study Dept. |
| Date of registration: | 08.02.2022 |
| Date of assignment: | 08.02.2022 |
| Confirmed by Study dept. on: | 28.02.2022 |
| Guidelines |
| Some optimization problems are so hard that they cannot be approximated within reasonable approximation bounds, and at the same time they are not fixed-parameter tractable. In this case it may still be possible to combine the two paradigms and find parameterized approximation algorithms. The aim of this project is to develop a deep understanding of the techniques used in both the field of approximation and fixed-parameter tractability, and then combine these to solve such hard problems using algorithms that approximate the solution with a running time that depends on some parameter. |
| References |
| [1] M. Cygan, FV Fomin, l. Kowalik, D. Lokshtanov, D. Marx, MA. Pilipczuk, Mi. Pilipczuk, S. Saurabh: Parameterized Algorithms
[2] V. Vazirani: Approximation Algorithms [3] D. Williamson, D. Shmoys: The Design of Approximation Algorithms [4] R. Downey, M. Fellows: Fundamentals of Parameterized Complexity [5] A. E. Feldmann, Karthik C. S., E. Lee, P. Manurangsi: A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms. |