The maximum box problem and its application to data analysis

Given two finite sets of points X+ and X- in R-n, the maximum box problem consists of finding an interval (" box") B = {x:l less than or equal to x less than or equal to u} such that B boolean AND X- =0, and the cardinality of B boolean AND X- is maximized. A simple generalization can be obtained by instead maximizing a weighted sum of the elements of B boolean AND X-. While polynomial for any fixed n, the maximum box problem is NP-hard in general. We construct an efficient branch-and-bound algorithm for this problem and apply it to a standard problem in data analysis. We test this method on nine data sets, seven of which are drawn from the UCI standard machine learning repository.