Français Anglais
Accueil Annuaire Plan du site
Home > Research results > Dissertations & habilitations
Research results
Ph.D de LE GUIBAN Kaourintin
LE GUIBAN Kaourintin
Group : Graphs, ALgorithms and Combinatorics


Starts on 01/10/2014
Advisor : TOMASIK, Joanna
[RIMMEL Arpad et WEISSER Marc-Antoine]

Funding : contrat doctoral du Ministère
Affiliation : Centrale Supélec
Laboratory :

Defended on 24/01/2018, committee :
Directeur de thèse :
- Mme Joanna TOMASIK CentraleSupélec

Rapporteurs :
- M. Jarosław BYRKA University of Wrocław
- M. Tristan CAZENAVE Université Paris-Dauphine

Examinateurs :
- Mme Cristina BAZGAN Université Paris-Dauphine
- M. Yannis MANOUSSAKIS Université Paris-Sud
- M. Arpad RIMMEL CentraleSupélec
- M. Marc-Antoine WEISSER CentraleSupélec
- M. Bertrand LE CUN Google Inc.

Research activities :

Abstract :
A Latin Hypercube Design (LHD) is a set of n points in dimension k with integer coordinates contained in a hypercube of size n k , such that its points do not share a coordinate on any dimension. In maximin LHDs the separation distance, i.e. the minimal distance between two points, is maximal. Maximin LHDs are widely used in metamodeling thanks to their space filling and noncollapsing properties which make them appropriate for sampling. As most work concerning LHDs focused on heuristic algorithms to produce them, we decided to make a detailed study of this problem, including its complexity, approximability, and the design of practical heuristic algorithms. To conduct this study, we generalized the maximin LHD construction problem by defining the maximin partial Latin Hypercube completion problem: given a partial LHD (an LHD with missing points), complete it with the maximum separation distance possible. The subproblem where the partial LHD is initially empty corresponds to the classical LHD construction problem. We studied the complexity of the completion problem and proved its NP-completeness for all norms in dimensions k ≥ 3, and for usual norms (i.e. norms Lp, with p ∈ N and norm L∞) on the plane. As we did not determine the complexity of the subproblem, we searched for performance guarantees of algorithms which may be designed for both problems. On the one hand, we found that the completion problem is inapproximable for all norms in dimensions k ≥ 3. We also gave a weaker inapproximation result for norm L∞ in dimension k = 2. On the other hand, we designed an approximation algorithm for the construction problem which we proved using two new upper bounds we introduced. Besides the theoretical aspect of this study, we worked on heuristic algorithms adapted for these problems, focusing primarily on the Simulated Annealing metaheuristic. We proposed a new evaluation function for the construction problem and new mutations for both the construction and completion problems, improving the results found in the literature. We observed that the behaviour of the completion problem changed depending on the number of points in the initial pLHD, calling for the use of different mutations. Taking advantage of this fact, we enriched the Simulated Annealing algorithm by using a bandit method to choose the most appropriate mutation on the fly, outperforming both mutations for intermediate number of points preset.

Ph.D. dissertations & Faculty habilitations

In this thesis, we propose a formal energy model which allows an analytical study of energy consumption, for the first time in the context of population protocols. Population protocols model one special kind of sensor networks where anonymous and uniformly bounded memory sensors move unpredictably and communicate in pairs. To illustrate the power and the usefulness of the proposed energy model, we present formal analyses on time and energy, for the worst and the average cases, for accomplishing the fundamental task of data collection. Two power-aware population protocols, (deterministic) EB-TTFM and (randomized) lazy-TTF, are proposed and studied for two different fairness conditions, respectively. Moreover, to obtain the best parameters in lazy-TTF, we adopt optimization techniques and evaluate the resulting performance by experiments. Then, we continue the study on optimization for the poweraware data collection problem in wireless body area networks. A minmax multi-commodity netow formulation is proposed to optimally route data packets by minimizing the worst power consumption. Then, a variable neighborhood search approach is developed and the numerical results show its efficiency. At last, a stochastic optimization model, namely the chance constrained semidefinite programs, is considered for the realistic decision making problems with random parameters. A novel simulation-based algorithm is proposed with experiments on a real control theory problem. We show that our method allows a less conservative solution, than other approaches, within reasonable time.