  


The Maximum Box Problem and its Application to Data Analysis
Jonathan Eckstein (jecksteirutcor.rutgers.edu) 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 NPcomplete in general. We construct an efficient branchandbound 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 (DataMining ) Citation: Research Report RRR 42002 RUTCOR, Rutgers University 640 Bartholomew Road Piscataway, NJ 08854 January 2002 Download: [Postscript] Entry Submitted: 01/16/2002 Modify/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  