Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of 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