Datum / čas
Date(s) - 19.01.
15:00 - 17:00
Kategorie ne Kategorie
Dvir Shabtay: On the Parameterized Complexity of Machine Scheduling Problems
The main goal of parameterized complexity is to try to design algorithms that are capable of solving (in reasonable time) hard problems in cases where some predefined problem parameters are of limited size. This theory was developed in the early 90s, contributing to many new techniques in the area of algorithmic design ever since. In this talk we survey the main aspects of parametrized complexity, and highlight its applicability to the area of scheduling. We also discuss some challenges and open problems for future research.