
Ph.D de LE GUIBAN Kaourintin 


LE GUIBAN Kaourintin
Ph.D
Group : Graphs, ALgorithms and Combinatorics
.
Starts on 01/10/2014
Advisor : TOMASIK, Joanna
[RIMMEL Arpad et WEISSER MarcAntoine]
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é ParisDauphine
Examinateurs :
 Mme Cristina BAZGAN Université ParisDauphine
 M. Yannis MANOUSSAKIS Université ParisSud
 M. Arpad RIMMEL CentraleSupélec
 M. MarcAntoine 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 NPcompleteness 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 


.POWERAWARE PROTOCOLS FOR WIRELESS SENSOR NETWORKSIn 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 poweraware population
protocols, (deterministic) EBTTFM and (randomized)
lazyTTF, are proposed and studied for two
different fairness conditions, respectively. Moreover,
to obtain the best parameters in lazyTTF,
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 multicommodity 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
simulationbased 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. USE OF INTRISIC MOTIVATIONS IN REINFORCEMENT LEARNING. APPLICATION TO SECURITY IN MULTIAGENT SYSTEMS




