PhD defence Arman Rouhani

Supervisor: Dr. André Berger

Co-supervisor: Dr. Marc Schröder

Keywords: Approximation Algorithms, Machine Scheduling, Distributed Systems, Fair Resource Allocation

 

"Approximation in Scheduling: From Decentralized Systems to Fair Allocation"

 

This thesis considers several scheduling problems inspired by practical   applications. It uses mathematical techniques to formulate these problems, analyze their structure, and design efficient algorithms that find optimal solutions whenever possible or provide provable approximation guarantees when the problems are computationally hard.

The first part studies decentralized scheduling, where individual decision-makers act in their own interest. The goal is to understand the effect of these individual decisions on the overall efficiency of the system.

The second part considers scheduling problems in which tasks must follow a fixed order to be processed on each machine and meet given deadlines, with the objective of using as few machines as possible.

The final part studies the fair allocation of resources under a limited budget and develops a new randomized algorithm for constructing feasible allocations while preserving guarantees on cost and allocation quality.

Click here for the full dissertation.       

Click here for the live stream.