Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Given n points in the s-dimensional unit cube, we consider the problem of finding a subinterval of minimum or maximum volume that contains exactly k of the n points. We give integer programming formulations of these problems and techniques to tackle their resolution. These optimal volume problems are used in an algorithm to compute the star discrepancy of n points in the s-dimensional unit cube. We propose an ultimately convergent strategy that gradually reduces the size of an interval containing this value. Results of some star discrepancy experiments and an empirical study of the computation time of the method are presented.
Corentin Jean Dominique Fivet, Jonas Warmuth, Jan Friedrich Georg Brütting