Adaptive Algorithms: Trade-off between Quality and Performances
- Niveau : Master recherche
- Responsable : Denis Trystram (Denis.Trystram@imag.fr)
- Mots-clés : portfolio of algorithms, multi-objective optimization
- Duration : 4 to 6 months
Responsables
Denis Trystram, Professeur Grenoble INP, LIG-MOAIS
Joachim Lepping, INRIA, LIG-MOAIS
Description
Considering the evolution of computing systems and practices, it is nowadays crucial to apply mechanisms that allow algorithms to flexibly react to environmental changes. This might include the addition or breakdowns of machines or congestions of communication links etc. Further, algorithms should be able to interactively adapt to the targeted applications. Usually, such mechanisms are integrated in the programming environment or are considered as part of the algorithm design itself. Alternatively, adaptive algorithms inherently provide mechanism to change its behavior according to potential changes on the data. On the one hand, an adaptive algorithm realizes a selection of the best algorithm when multiple different algorithms are available. On the other hand, the adaptation focuses on a combination where the whole adaptive algorithm divides itself into several phases while in each phase different algorithms are used successively.
In more detail, we are interested in optimizing the performance of a so-called "portfolio of algorithms" using machine learning techniques. The goal is to efficiently solve a series of instances using a set of already available algorithms. This question can be seen as finding the best compromise between the execution time of an algorithm on an instance and the accuracy obtained by this algorithm. The only way that exists today to solve this kind of problem is to study algorithms « online ». There, the algorithm selection decisions are made blindly, which is generally ineffective. Another approach addresses the overall problem with recently (preferably randomized) techniques from the area of multi-objective optimization. There, the whole set of trade-offs between execution time and solution accuracy can be computed.
In this project, we aim to apply methods from multi-objective optimization to determine the trade-offs between execution time and accuracy in the context of job scheduling algorithms. For this problem domain we have several algorithms available that can serve as basic components of an overall algorithms portfolio. For example, and LIST-scheduling algorithm is usually fast but not always efficient while exact method are very precise but also very computationally expensive. Further, we have for certain problems heuristics which run fast but have not solution guarantees.