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

Eckstein, Jonathan; Hammer, Peter L.; Liu, Ying; Nediak, Mikhail; Simeone, Bruno

Comput. Optim. Appl. 23, No. 3, 285-298 (2002).

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