2024-11-08
Présentation lors du Workshop International en Combinatoire et Géométrie sur les algorithmes d'approximation de données.
In this talk, we discuss two problems related to data approximation: combinatorial discrepancy and simplicial partitions. We present efficient algorithms to solve them in geometric settings. For the former we build an algorithm based on a new mathematical game that we introduce and the celebrated result from Lovett and Meka that solves the set discrepancy question for abstract set system. For the latter, we present a fast algorithm that heuristically minimizes a potential function that we show lead to low crossing number partitions when they exist.
Diapositives