The maximum box problem and its application to data analysis

Jonathan Eckstein; Peter L. Hammer; Ying Liu; Mikhail Nediak; Bruno Simeone

doi:10.1023/A:1020546910706

The maximum box problem and its application to data analysis

Jonathan Eckstein, Peter L. Hammer, Ying Liu, Mikhail Nediak, Bruno Simeone

Rutgers Business School, Management & Information Systems

Research output: Contribution to journal › Article › peer-review

60 Scopus citations

Abstract

Given two finite sets of points X⁺ and X^- in ℝⁿ, the maximum box problem consists of finding an interval ("box") B = {x : 1 ≤ x ≤ u} such that B ∩ X^- = 0, 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 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.

Original language	English (US)
Pages (from-to)	285-298
Number of pages	14
Journal	Computational Optimization and Applications
Volume	23
Issue number	3
DOIs	https://doi.org/10.1023/A:1020546910706
State	Published - Dec 2002

All Science Journal Classification (ASJC) codes

Control and Optimization
Computational Mathematics
Applied Mathematics

Keywords

Branch and bound
Data analysis
Discrete optimization
Patterns

Access to Document

10.1023/A:1020546910706

Cite this

@article{6511e2128b5642bc8b130d8f5a830f0d,

title = "The maximum box problem and its application to data analysis",

abstract = "Given two finite sets of points X+ and X- in ℝn, the maximum box problem consists of finding an interval ({"}box{"}) B = {x : 1 ≤ x ≤ u} such that B ∩ X- = 0, 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 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.",

keywords = "Branch and bound, Data analysis, Discrete optimization, Patterns",

author = "Jonathan Eckstein and Hammer, {Peter L.} and Ying Liu and Mikhail Nediak and Bruno Simeone",

note = "Funding Information: This work was supported in part by NSF grants CCR-9902092 and DMS-9806389, and ONR grant N00014-92-J-1375. The work of the third and fourth authors was also supported in part by DIMACS.",

year = "2002",

month = dec,

doi = "10.1023/A:1020546910706",

language = "English (US)",

volume = "23",

pages = "285--298",

journal = "Computational Optimization and Applications",

issn = "0926-6003",

publisher = "Springer Netherlands",

number = "3",

}

TY - JOUR

T1 - The maximum box problem and its application to data analysis

AU - Eckstein, Jonathan

AU - Hammer, Peter L.

AU - Liu, Ying

AU - Nediak, Mikhail

AU - Simeone, Bruno

N1 - Funding Information: This work was supported in part by NSF grants CCR-9902092 and DMS-9806389, and ONR grant N00014-92-J-1375. The work of the third and fourth authors was also supported in part by DIMACS.

PY - 2002/12

Y1 - 2002/12

N2 - Given two finite sets of points X+ and X- in ℝn, the maximum box problem consists of finding an interval ("box") B = {x : 1 ≤ x ≤ u} such that B ∩ X- = 0, 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 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.

AB - Given two finite sets of points X+ and X- in ℝn, the maximum box problem consists of finding an interval ("box") B = {x : 1 ≤ x ≤ u} such that B ∩ X- = 0, 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 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.

KW - Branch and bound

KW - Data analysis

KW - Discrete optimization

KW - Patterns

UR - http://www.scopus.com/inward/record.url?scp=0036891189&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0036891189&partnerID=8YFLogxK

U2 - 10.1023/A:1020546910706

DO - 10.1023/A:1020546910706

M3 - Article

AN - SCOPUS:0036891189

SN - 0926-6003

VL - 23

SP - 285

EP - 298

JO - Computational Optimization and Applications

JF - Computational Optimization and Applications

IS - 3

ER -

The maximum box problem and its application to data analysis

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this