Name
Abstract | ||
|---|---|---|
Given two finite sets of points X+ and X− in \Bbb Rn, 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 \cal{NP}-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. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1023/A:1020546910706 | Comp. Opt. and Appl. |
Keywords | Field | DocType |
discrete optimization,branch and bound,data analysis,patterns | Discrete mathematics,Combinatorics,Data set,Branch and bound,Mathematical optimization,Finite set,Polynomial,Discrete optimization,Cardinality,Mathematics | Journal |
Volume | Issue | ISSN |
23 | 3 | 1573-2894 |
Citations | PageRank | References |
31 | 1.59 | 4 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jonathan Eckstein | 1 | 37 | 3.42 |
| Peter L. Hammer | 2 | 1996 | 288.93 |
| Ying Liu | 3 | 41 | 2.11 |
| Mikhail Nediak | 4 | 180 | 11.73 |
| Bruno Simeone | 5 | 496 | 54.36 |