Supervision : Carola DOERR

Efficient algorithms for discrepancy subset selection

Given a point set of size n, we want to find the subset of size m of minimal star discrepancy (a specific measure of discrepancy). Initial results obtained recently by C. Doerr and L. Paquete (Coimbra University) were promising and during this thesis we will aim to provide a more formal approach to the problem, as well as provide new algorithms and theoretical bounds, both for the exact problem as for approximations. Our approach will be both theoretical, via complexity analysis and algorithm development, and practical, with extensive testing of our algorithms and searching for the different applications of our new approach to discrepancy. We will be working with different branches of mathematics and computer science (Operations, Research, Algorithmic Theory, Discrepancy Theory) and it is highly likely that that the resolution of our problem will bring us to develop new tools or proofs in these different fields.

2022-2024 Publications

• 2024
  • F. Clément, C. Doerr, L. Paquete : “Heuristic approaches to obtain low-discrepancy point sets via subset selection”, Journal of Complexity, vol. 83, pp. 101852, (Elsevier) (2024)
• 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)