×

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
PDF BibTeX XML Cite
Full Text: DOI