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/2002
Entry Accepted: 01/16/2002
Entry Last Modified: 01/16/2002

Modify/Update this entry