The Maximum Box Problem and its Application to Data Analysis View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2002-12

AUTHORS

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

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. More... »

PAGES

285-298

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1023/a:1020546910706

DOI

http://dx.doi.org/10.1023/a:1020546910706

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1045163626


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Rutgers University", 
          "id": "https://www.grid.ac/institutes/grid.430387.b", 
          "name": [
            "Rutgers Business School and RUTCOR, Rutgers University, 640 Bartholomew Road, 08854, Piscataway, NJ, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Eckstein", 
        "givenName": "Jonathan", 
        "id": "sg:person.016161530511.35", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016161530511.35"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Rutgers University", 
          "id": "https://www.grid.ac/institutes/grid.430387.b", 
          "name": [
            "RUTCOR, Rutgers University, 640 Bartholomew Road, 08854, Piscataway, NJ, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Hammer", 
        "givenName": "Peter L.", 
        "id": "sg:person.015740461177.00", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015740461177.00"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Rutgers University", 
          "id": "https://www.grid.ac/institutes/grid.430387.b", 
          "name": [
            "RUTCOR, Rutgers University, 640 Bartholomew Road, 08854, Piscataway, NJ, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Liu", 
        "givenName": "Ying", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Rutgers University", 
          "id": "https://www.grid.ac/institutes/grid.430387.b", 
          "name": [
            "RUTCOR, Rutgers University, 640 Bartholomew Road, 08854, Piscataway, NJ, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Nediak", 
        "givenName": "Mikhail", 
        "id": "sg:person.010157410531.81", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010157410531.81"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "name": [
            "Department of Statistics, \u201cLa Sapienza\u201d, University, Piazzale Aldo Moro 5, 00185, Rome, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Simeone", 
        "givenName": "Bruno", 
        "id": "sg:person.012600006066.78", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012600006066.78"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/bf02283750", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009714991", 
          "https://doi.org/10.1007/bf02283750"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02283750", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009714991", 
          "https://doi.org/10.1007/bf02283750"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-0-387-35514-6_2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026657599", 
          "https://doi.org/10.1007/978-0-387-35514-6_2"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02614316", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032847525", 
          "https://doi.org/10.1007/bf02614316"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02614316", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032847525", 
          "https://doi.org/10.1007/bf02614316"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0167-5060(08)70351-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1034090353"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1023/a:1007608224229", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1047825454", 
          "https://doi.org/10.1023/a:1007608224229"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/69.842268", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061213820"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/69.842268", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061213820"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2002-12", 
    "datePublishedReg": "2002-12-01", 
    "description": "Given two finite sets of points X+ and X\u2212 in n, the maximum box problem consists of finding an interval (\u201cbox\u201d) B = {x : l \u2264 x \u2264 u} such that B \u2229 X\u2212 = \u2205, and the cardinality of B \u2229 X+ is maximized. A simple generalization can be obtained by instead maximizing a weighted sum of the elements of B \u2229 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.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1023/a:1020546910706", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1042206", 
        "issn": [
          "0926-6003", 
          "1573-2894"
        ], 
        "name": "Computational Optimization and Applications", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "3", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "23"
      }
    ], 
    "name": "The Maximum Box Problem and its Application to Data Analysis", 
    "pagination": "285-298", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "d7213d8941c48f3a0b2e69e668c9803f41d6d516f2a0f515c416168e4a69fb0b"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1023/a:1020546910706"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1045163626"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1023/a:1020546910706", 
      "https://app.dimensions.ai/details/publication/pub.1045163626"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T00:14", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8695_00000507.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1023%2FA%3A1020546910706"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1023/a:1020546910706'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1023/a:1020546910706'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1023/a:1020546910706'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1023/a:1020546910706'


 

This table displays all metadata directly associated to this object as RDF triples.

113 TRIPLES      21 PREDICATES      33 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1023/a:1020546910706 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author Nbfd12a1a9b9e48c0b99abbca4c291ea3
4 schema:citation sg:pub.10.1007/978-0-387-35514-6_2
5 sg:pub.10.1007/bf02283750
6 sg:pub.10.1007/bf02614316
7 sg:pub.10.1023/a:1007608224229
8 https://doi.org/10.1016/s0167-5060(08)70351-0
9 https://doi.org/10.1109/69.842268
10 schema:datePublished 2002-12
11 schema:datePublishedReg 2002-12-01
12 schema:description 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.
13 schema:genre research_article
14 schema:inLanguage en
15 schema:isAccessibleForFree false
16 schema:isPartOf N191be04888e4481d84eb1630e6ae5566
17 N45665da57eb04d58b60c158574e4f994
18 sg:journal.1042206
19 schema:name The Maximum Box Problem and its Application to Data Analysis
20 schema:pagination 285-298
21 schema:productId N1404983e879a4028a4dec63b6a9c8986
22 N654f9bc9f2e04200a8f712ad214d450c
23 Na64000d126f5449caa1a9e96b10595d3
24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045163626
25 https://doi.org/10.1023/a:1020546910706
26 schema:sdDatePublished 2019-04-11T00:14
27 schema:sdLicense https://scigraph.springernature.com/explorer/license/
28 schema:sdPublisher N31e8b12d73334938a9197fb830b69c8a
29 schema:url http://link.springer.com/10.1023%2FA%3A1020546910706
30 sgo:license sg:explorer/license/
31 sgo:sdDataset articles
32 rdf:type schema:ScholarlyArticle
33 N119ff1e77f6d4872bc87197dd0eb5013 rdf:first N65ceec86f6fc49e0b8fdbc2906598b97
34 rdf:rest Na8e9191cc0c94b6aae7ce23e0e9ccf48
35 N1404983e879a4028a4dec63b6a9c8986 schema:name doi
36 schema:value 10.1023/a:1020546910706
37 rdf:type schema:PropertyValue
38 N191be04888e4481d84eb1630e6ae5566 schema:issueNumber 3
39 rdf:type schema:PublicationIssue
40 N31e8b12d73334938a9197fb830b69c8a schema:name Springer Nature - SN SciGraph project
41 rdf:type schema:Organization
42 N45665da57eb04d58b60c158574e4f994 schema:volumeNumber 23
43 rdf:type schema:PublicationVolume
44 N654f9bc9f2e04200a8f712ad214d450c schema:name readcube_id
45 schema:value d7213d8941c48f3a0b2e69e668c9803f41d6d516f2a0f515c416168e4a69fb0b
46 rdf:type schema:PropertyValue
47 N65ceec86f6fc49e0b8fdbc2906598b97 schema:affiliation https://www.grid.ac/institutes/grid.430387.b
48 schema:familyName Liu
49 schema:givenName Ying
50 rdf:type schema:Person
51 N780319c92ad34bf3808cedd10cc032ca schema:name Department of Statistics, “La Sapienza”, University, Piazzale Aldo Moro 5, 00185, Rome, Italy
52 rdf:type schema:Organization
53 N97214b8280e34562afc06f46cb4dc7c5 rdf:first sg:person.012600006066.78
54 rdf:rest rdf:nil
55 Na64000d126f5449caa1a9e96b10595d3 schema:name dimensions_id
56 schema:value pub.1045163626
57 rdf:type schema:PropertyValue
58 Na8e9191cc0c94b6aae7ce23e0e9ccf48 rdf:first sg:person.010157410531.81
59 rdf:rest N97214b8280e34562afc06f46cb4dc7c5
60 Nb4d5464cddb14ecf8d958e02dc1a0f40 rdf:first sg:person.015740461177.00
61 rdf:rest N119ff1e77f6d4872bc87197dd0eb5013
62 Nbfd12a1a9b9e48c0b99abbca4c291ea3 rdf:first sg:person.016161530511.35
63 rdf:rest Nb4d5464cddb14ecf8d958e02dc1a0f40
64 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
65 schema:name Information and Computing Sciences
66 rdf:type schema:DefinedTerm
67 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
68 schema:name Artificial Intelligence and Image Processing
69 rdf:type schema:DefinedTerm
70 sg:journal.1042206 schema:issn 0926-6003
71 1573-2894
72 schema:name Computational Optimization and Applications
73 rdf:type schema:Periodical
74 sg:person.010157410531.81 schema:affiliation https://www.grid.ac/institutes/grid.430387.b
75 schema:familyName Nediak
76 schema:givenName Mikhail
77 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010157410531.81
78 rdf:type schema:Person
79 sg:person.012600006066.78 schema:affiliation N780319c92ad34bf3808cedd10cc032ca
80 schema:familyName Simeone
81 schema:givenName Bruno
82 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012600006066.78
83 rdf:type schema:Person
84 sg:person.015740461177.00 schema:affiliation https://www.grid.ac/institutes/grid.430387.b
85 schema:familyName Hammer
86 schema:givenName Peter L.
87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015740461177.00
88 rdf:type schema:Person
89 sg:person.016161530511.35 schema:affiliation https://www.grid.ac/institutes/grid.430387.b
90 schema:familyName Eckstein
91 schema:givenName Jonathan
92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016161530511.35
93 rdf:type schema:Person
94 sg:pub.10.1007/978-0-387-35514-6_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026657599
95 https://doi.org/10.1007/978-0-387-35514-6_2
96 rdf:type schema:CreativeWork
97 sg:pub.10.1007/bf02283750 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009714991
98 https://doi.org/10.1007/bf02283750
99 rdf:type schema:CreativeWork
100 sg:pub.10.1007/bf02614316 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032847525
101 https://doi.org/10.1007/bf02614316
102 rdf:type schema:CreativeWork
103 sg:pub.10.1023/a:1007608224229 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047825454
104 https://doi.org/10.1023/a:1007608224229
105 rdf:type schema:CreativeWork
106 https://doi.org/10.1016/s0167-5060(08)70351-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034090353
107 rdf:type schema:CreativeWork
108 https://doi.org/10.1109/69.842268 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061213820
109 rdf:type schema:CreativeWork
110 https://www.grid.ac/institutes/grid.430387.b schema:alternateName Rutgers University
111 schema:name RUTCOR, Rutgers University, 640 Bartholomew Road, 08854, Piscataway, NJ, USA
112 Rutgers Business School and RUTCOR, Rutgers University, 640 Bartholomew Road, 08854, Piscataway, NJ, USA
113 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...