Seminar Room, ground floor (Building IMAG)
16 février 2017 - 14h00
Trade-offs in Resource Allocation Problems (Phd Defense)
par Abhinav Srivastav de Verimag
Abstract: The thesis is focused on the study of trade-offs in resource allocation problems. The first part of this thesis deals with the study of heuristic based approaches for the approximation of Pareto fronts. We propose a new stochastic local search algorithm for solving multi-objective combinatorial optimization problems. We embed our technique into a genetic framework and show that this method improves upon the existing Pareto local search algorithm on several instances of bi-objective and tri-objective quadratic assignment problem.
In the second part of this thesis, we focus on non-preemptive scheduling algorithms. Here, we first study the online problem of minimizing maximum stretch on a single machine. We present both positive and negative theoretical results. Furthermore, we study the problem of minimizing stretch/flow time on a single machine in a recently proposed rejection model. We show that there exists an O(1)-approximation ratio for minimizing the flow time. We further extend the idea used here to show that there exists an O(1)-approximation ratio for minimizing the average stretch on a single machine. Lastly, we study the weighted average flow time minimization problem in online settings. We present a mathematical programming based framework that unifies multiple resource augmentation. Then, we develop a scheduling algorithm based on the concept of duality and show that there exists an O(1)-competitive algorithm for solving the weighted average flow time problem on a set of unrelated machines. Furthermore, we extended this idea to the problem of minimizing weighted ell_k norms of flow time on a set of unrelated machines
Jury:
Oded Maler - Directeur de these
Denis Trystram - Co-Directeur de these
Adi Rosen - Rapporteur
Monaldo Mastrolilli - Rapporteur
Marie Christine Rousset - Examinateur
Lothar Thiele - Examinateur
Seffi Naor - Examinateur
Daniel Vanderpooten - Examinateur
