The maximum box problem and its application to data analysis. (English) Zbl 1028.90039

Summary: Given two finite sets of points \(X^+\) and \(X^-\) in \(\mathbb{R}^n\), the maximum box problem consists of 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-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.


90C27 Combinatorial optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
Full Text: DOI