Given two finite sets of points $X^+$ and $X^-$ in $\R^n$, the maximum box problem consists in finding an interval (``box'') $B=\{x : l \leq x \leq u\}$ such that $B\cap X^-=\emptyset$, and the cardinality of $B\cap X^+$ is maximized. A simple generalization can be obtained by instead maximizing a weighted sum of the elements of $B\cap X^+$. While polynomial for any fixed $n$, the maximum box problem is NP-complete 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.
Citation
Research Report RRR 4-2002 RUTCOR, Rutgers University 640 Bartholomew Road Piscataway, NJ 08854 January 2002
Article
View The Maximum Box Problem and its Application to Data Analysis