The Maximum Box Problem and its Application to Data Analysis |
| |
Authors: | Jonathan Eckstein Peter L Hammer Ying Liu Mikhail Nediak Bruno Simeone |
| |
Institution: | (1) Rutgers Business School and RUTCOR, Rutgers University, 640 Bartholomew Road, Piscataway, NJ 08854, USA;(2) RUTCOR, Rutgers University, 640 Bartholomew Road, Piscataway, NJ 08854, USA;(3) Department of Statistics, La Sapienza, University, Piazzale Aldo Moro 5, 00185 Rome, Italy |
| |
Abstract: | Given two finite sets of points X
+ and X
– in
n
, the maximum box problem consists of finding an interval (box) B = {x : l x u} such that B X
– = , and the cardinality of B X
+ is maximized. A simple generalization can be obtained by instead maximizing a weighted sum of the elements of B X
+. While polynomial for any fixed n, the maximum box problem is
-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. |
| |
Keywords: | discrete optimization branch and bound data analysis patterns |
本文献已被 SpringerLink 等数据库收录! |
|