
Ph.D de 


Ph.D
Group : Graphs, ALgorithms and Combinatorics
Hypercubes latins maximin pour l’échantillonnage de systèmes complexes
Starts on 01/10/2014
Advisor : TOMASIK, Joanna
[RIMMEL Arpad et WEISSER MarcAntoine]
Funding : Contrat doctoral uniquement recherche
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 


LINKED DATA AT UNIVERSITY : THE LINKEDWIKI PLATFORMThe Center for Data Science of the University of ParisSaclay deployed a platform compatible with Linked Data in 2016. Because researchers face many difficulties utilizing these technologies, an approach and then a platform we call LinkedWiki were designed and tested over the university’s cloud (IAAS) to enable the creation of modular virtual search environments (VREs) compatible with Linked Data. We are thus able to offer researchers a means to discover, produce and reuse the research data available within the Linked Open Data, i.e., the global information system emerging at the scale of the internet. This experience enabled us to demonstrate that the operational use of Linked Data within a university is perfectly possible with this approach. However, some problems persist, such as (i) the respect of protocols and (ii) the lack of adapted tools to interrogate the Linked Open Data with SPARQL. We propose solutions to both these problems. In order to be able to verify the respect of a SPARQL protocol within the Linked Data of a university, we have created the SPARQL Score indicator which evaluates the compliance of the SPARQL services before their deployments in a university’s information system. In addition, to help researchers interrogate the LOD, we implemented a SPARQLetsFinder, a demonstrator which shows that it is possible to facilitate the design of SPARQL queries using autocompletion tools without prior knowledge of the RDF schemas within the LOD. LINKED DATA AT UNIVERSITY : THE LINKEDWIKI PLATFORMThe Center for Data Science of the University of ParisSaclay deployed a platform compatible with Linked Data in 2016. Because researchers face many difficulties utilizing these technologies, an approach and then a platform we call LinkedWiki were designed and tested over the university’s cloud (IAAS) to enable the creation of modular virtual search environments (VREs) compatible with Linked Data. We are thus able to offer researchers a means to discover, produce and reuse the research data available within the Linked Open Data, i.e., the global information system emerging at the scale of the internet. This experience enabled us to demonstrate that the operational use of Linked Data within a university is perfectly possible with this approach. However, some problems persist, such as (i) the respect of protocols and (ii) the lack of adapted tools to interrogate the Linked Open Data with SPARQL. We propose solutions to both these problems. In order to be able to verify the respect of a SPARQL protocol within the Linked Data of a university, we have created the SPARQL Score indicator which evaluates the compliance of the SPARQL services before their deployments in a university’s information system. In addition, to help researchers interrogate the LOD, we implemented a SPARQLetsFinder, a demonstrator which shows that it is possible to facilitate the design of SPARQL queries using autocompletion tools without prior knowledge of the RDF schemas within the LOD. CONSTRUCTION, éVOLUTION ET ENRICHISSEMENT D'UNE ONTOLOGIE CONTEXTUELLE POUR UNE BASE DE CONNAISSANCES MULTIUSAGE DANS LE DOMAINE DU BâTIMENT




