- The Maximum Box Problem and its Application to Data Analysis Jonathan Eckstein (jecksteirutcor.rutgers.edu) Peter L. Hammer (hammerrutcor.rutgers.edu) Ying Liu (yingliurutcor.rutgers.edu) Mikhail S. Nediak (msnediakrutcor.rutgers.edu) Bruno Simeone (marsalisrosd.sta.uniroma1.it) Abstract: 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. Keywords: Maximum Box, Branch and Bound, Data Analysis Category 1: Combinatorial Optimization Category 2: Applications -- Science and Engineering (Data-Mining ) Citation: Research Report RRR 4-2002 RUTCOR, Rutgers University 640 Bartholomew Road Piscataway, NJ 08854 January 2002 Download: [Postscript]Entry Submitted: 01/16/2002Entry Accepted: 01/16/2002Entry Last Modified: 01/16/2002Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.