## 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.

### MSC:

 90C27 Combinatorial optimization 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut

### Keywords:

discrete optimization; branch and bound; data analysis; patterns
Full Text: