Optimal volume subintervals with k points and star discrepancy via integer programming

Autor:	Eric Thiémard
Rok vydání:	2001
Předmět:	Discrete mathematics Optimality criterion Linear programming Star discrepancy General Mathematics Computation Integer programming Interval (mathematics) Management Science and Operations Research Star (graph theory) Computational geometry Combinatorics Unit cube Software Mathematics
Zdroj:	Mathematical Methods of Operations Research (ZOR). 54:21-45
ISSN:	1432-5217 1432-2994
DOI:	10.1007/s001860100141
Popis:	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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::7b110977d2e75de2ebace65f593c7c93 https://doi.org/10.1007/s001860100141 Zobrazit plný text záznamu Plný text ve formátu PDF