Direction de recherche : Carola DOERR

Algorithmes efficaces pour la sélection de sous-ensembles à faible discrépance

À partir d'un ensemble de points de taille n, nous cherchons à trouver le sous-ensemble de taille m de discrépance minimale, où l'on considère ici la "star discrepancy L_inf" comme mesure de discrépance. Ce projet se base sur des résultats initiaux prometteurs de C. Doerr et L. Paquete (Univ. Coimbra). Nous aborderons lors de cette thèse une analyse formelle du problème via des résultats précis sur sa complexité et des algorithmes d'approximation possibles ainsi qu'un aspect plus pratique via la recherche d'applications possibles de nos résultats et des tests de nos algorithmes. Ce sujet se trouvant à la jonction de plusieurs domaines (Recherche Opérationnelle, Algorithmie, théorie mathématique autour de la discrépance), il est probable que nous ayons à développer de nouvelles méthodes dans ces différents domaines lors de la thèse.

Publications 2022-2023

• 2023
  • F. Clément, D. Vermetten, J. De Nobel, A. Jesus, L. Paquete, C. Doerr : “Computing Star Discrepancies with Numerical Black-Box Optimization Algorithms”, GECCO '23: Genetic and Evolutionary Computation Conference, Lisbon, Portugal, pp. 1330-1338, (ACM) (2023)
• 2022
  • F. Clément, C. Doerr, L. Paquete : “Star Discrepancy Subset Selection: Problem Formulation and Efficient Approaches for Low Dimensions”, Journal of Complexity, vol. 70, pp. 101645, (Elsevier) (2022)