Optimization Online


The Maximum Box Problem and its Application to Data Analysis

Jonathan Eckstein (jeckstei***at***rutcor.rutgers.edu)
Peter L. Hammer (hammer***at***rutcor.rutgers.edu)
Ying Liu (yingliu***at***rutcor.rutgers.edu)
Mikhail S. Nediak (msnediak***at***rutcor.rutgers.edu)
Bruno Simeone (marsalis***at***rosd.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society