The Maximum Box Problem and its Application to Data Analysis

Given two finite sets of points X⁺ and X^– in ⁿ, the maximum box problem consists of finding an interval (box) B = {x : l x u} such that B X^– = , and the cardinality of B X⁺ is maximized. A simple generalization can be obtained by instead maximizing a weighted sum of the elements of B X⁺. While polynomial for any fixed n, the maximum box problem is -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.