Algorithms for the star discrepancy subset selection problem

Abstract

As discrepâncias quantificam diferenças entre duas medições de conjuntos de pontos. A discrepância estrela é um tipo particular de discrepância com aplicações em áreas como a estatística e a geração de números pseudo-aleatórios. Pode ser definida como o supremo do valor absoluto da discrepância local para todos os pontos no hipercubo unitário. A selecção de subconjuntos baseada na discrepância estrela consiste em encontrar o subconjunto de k pontos de um conjunto de n pontos, n ≥ k, que minimiza a discrepância estrela. O objectivo deste trabalho é desenvolver algoritmos de branch and bound que sejam capazes de resolver este problema para um conjunto arbitrário de pontos, número de dimensões e valor de k. Foram desenvolvidas duas funções de bound que podem ser usadas para resolver este problema para qualquer número de dimensões, bem como um conjunto de melhorias para o algoritmo base de branch and bound. A nossa abordagem revelou uma melhoria evidente de desempenho, em multiplos cenários diferentes, quando comparada com um algoritmo simples de pesquisa que avalia todos os possíveis subconjuntos. Esta melhoria foi mais significativa para conjuntos de pontos num espaço com duas dimensões.---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Discrepancies quantify differences between two measurements of point sets. The star discrepancy is a particular type of discrepancy with application in areas such as statistics and pseudo-random number generation. It can be defined as the supremum of the absolute value of the local discrepancy for all points in the unit hypercube. The star discrepancy subset selection consists of finding the subset of k out of n points that minimizes the star discrepancy. The goal of this work is to develop branch-and-bound algorithms that are able to solve this problem for an arbitrary set of points, number of dimensions and value of k. We have developed two bounding functions that can be used to solve this problem for any number of dimensions, as well as a set of improvements to the base branch-and-bound algorithm. Our approach showed a clear increase in performance, on multiple different scenarios, when compared to a simple search algorithm that evaluates all possible subsets. This increase was most significant for point sets in a two-dimensional space.------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------