Approximation and Parameterized Algorithms for Scheduling Problems
In this thesis, we give new algorithmic results for NP-hard scheduling problems in the fields of approximation and parameterization. In the first part, we give constant-factor approximation algorithms for two scheduling problems, known as Coupled Task Scheduling and Preemptive Batch Scheduling. In the second part, we exclusively look at the problem of Scheduling on Uniform Machines, but with different objective functions, in different input settings (offline and online) and from different angles (parameterization and approximation).
Preview
Rights
Use and reproduction:
Please note that individual components of the publication may be subject to other licensing or copyright conditions.
Cite
Citation style:
Could not load citation form.