Clustering heuristics for set covering View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1993-05

AUTHORS

Renata Krystyna Kwatera, Bruno Simeone

ABSTRACT

We introduce a new class of set covering heuristics, based on clustering techniques. In its simplest form, a heuristic in this class may be described as follows: firstly, partition the column set into clusters formed by columns that are close to each other (e.g. in the Hamming distance sense). Then select a “best” (e.g. a cheapest) column in each cluster; if the selected columns form a coverC, then extract fromC a prime cover and stop; else, modify the partition (e.g. by increasing the number of clusters) and repeat. We describe two implementations of this general algorithmic strategy, relying on the Single Linkage and the Leader clustering algorithm, respectively. Numerical experiments performed on 72 randomly generated test problems with 200 or 400 rows and 1000 columns indicate that the above two heuristics often yield cheaper covers than other well-known (greedy-type) heuristics when the cost-range is not too narrow. More... »

PAGES

295-308

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bf02025300

DOI

http://dx.doi.org/10.1007/bf02025300

DIMENSIONS

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


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/0103", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Numerical and Computational Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Rome Tor Vergata", 
          "id": "https://www.grid.ac/institutes/grid.6530.0", 
          "name": [
            "Dipartimento di Fisica, Universit\u00e0 \u201cTor Vergata\u201d, via della Ricerca Scientifica 1, 00173, Rome, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kwatera", 
        "givenName": "Renata Krystyna", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Sapienza University of Rome", 
          "id": "https://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "Dipartimento di Statistica, Probabilit\u00e0 e Statistiche Applicate, Universit\u00e0 \u201cLa Sapienza\u201d, 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/bfb0120886", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1010250587", 
          "https://doi.org/10.1007/bfb0120886"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bfb0120886", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1010250587", 
          "https://doi.org/10.1007/bfb0120886"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01874392", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1020540312", 
          "https://doi.org/10.1007/bf01874392"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01874392", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1020540312", 
          "https://doi.org/10.1007/bf01874392"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0196-6774(81)90020-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1022335295"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0304-0208(08)73236-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032856118"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0167-6377(89)90002-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045066110"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0167-6377(89)90002-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045066110"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/321958.321975", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048192025"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tpami.1980.4767027", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061741699"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0211045", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841661"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/mnsc.25.4.329", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064719186"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/moor.4.3.233", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064724457"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/opre.23.1.74", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064728583"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.2307/2346439", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1101981384"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.2307/2346439", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1101981384"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1993-05", 
    "datePublishedReg": "1993-05-01", 
    "description": "We introduce a new class of set covering heuristics, based on clustering techniques. In its simplest form, a heuristic in this class may be described as follows: firstly, partition the column set into clusters formed by columns that are close to each other (e.g. in the Hamming distance sense). Then select a \u201cbest\u201d (e.g. a cheapest) column in each cluster; if the selected columns form a coverC, then extract fromC a prime cover and stop; else, modify the partition (e.g. by increasing the number of clusters) and repeat. We describe two implementations of this general algorithmic strategy, relying on the Single Linkage and the Leader clustering algorithm, respectively. Numerical experiments performed on 72 randomly generated test problems with 200 or 400 rows and 1000 columns indicate that the above two heuristics often yield cheaper covers than other well-known (greedy-type) heuristics when the cost-range is not too narrow.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/bf02025300", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1048429", 
        "issn": [
          "0254-5330", 
          "1572-9338"
        ], 
        "name": "Annals of Operations Research", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "5", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "43"
      }
    ], 
    "name": "Clustering heuristics for set covering", 
    "pagination": "295-308", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "0ebd4dcd5eaccb43b56f02eea93301f4d5dba18738c0fff480a292d25137c9cb"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf02025300"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1003094219"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf02025300", 
      "https://app.dimensions.ai/details/publication/pub.1003094219"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T11:30", 
    "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/0000000357_0000000357/records_99299_00000000.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007/BF02025300"
  }
]
 

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.1007/bf02025300'

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.1007/bf02025300'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf02025300'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf02025300'


 

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

108 TRIPLES      21 PREDICATES      39 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf02025300 schema:about anzsrc-for:01
2 anzsrc-for:0103
3 schema:author N957e4defb6c145faa8d11ce5f36a24ae
4 schema:citation sg:pub.10.1007/bf01874392
5 sg:pub.10.1007/bfb0120886
6 https://doi.org/10.1016/0167-6377(89)90002-3
7 https://doi.org/10.1016/0196-6774(81)90020-1
8 https://doi.org/10.1016/s0304-0208(08)73236-5
9 https://doi.org/10.1109/tpami.1980.4767027
10 https://doi.org/10.1137/0211045
11 https://doi.org/10.1145/321958.321975
12 https://doi.org/10.1287/mnsc.25.4.329
13 https://doi.org/10.1287/moor.4.3.233
14 https://doi.org/10.1287/opre.23.1.74
15 https://doi.org/10.2307/2346439
16 schema:datePublished 1993-05
17 schema:datePublishedReg 1993-05-01
18 schema:description We introduce a new class of set covering heuristics, based on clustering techniques. In its simplest form, a heuristic in this class may be described as follows: firstly, partition the column set into clusters formed by columns that are close to each other (e.g. in the Hamming distance sense). Then select a “best” (e.g. a cheapest) column in each cluster; if the selected columns form a coverC, then extract fromC a prime cover and stop; else, modify the partition (e.g. by increasing the number of clusters) and repeat. We describe two implementations of this general algorithmic strategy, relying on the Single Linkage and the Leader clustering algorithm, respectively. Numerical experiments performed on 72 randomly generated test problems with 200 or 400 rows and 1000 columns indicate that the above two heuristics often yield cheaper covers than other well-known (greedy-type) heuristics when the cost-range is not too narrow.
19 schema:genre research_article
20 schema:inLanguage en
21 schema:isAccessibleForFree false
22 schema:isPartOf N9c5cef0d1ba1418ba29165cb8c6a8682
23 Nbb83a2df2a31434babf14e36d0320382
24 sg:journal.1048429
25 schema:name Clustering heuristics for set covering
26 schema:pagination 295-308
27 schema:productId N0ae3c401103f4a04858d0ceeff0b776f
28 N4832045efafc407a92ef7a094cc162f5
29 N6483f82cb19249f0aa9f275c9df16869
30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003094219
31 https://doi.org/10.1007/bf02025300
32 schema:sdDatePublished 2019-04-11T11:30
33 schema:sdLicense https://scigraph.springernature.com/explorer/license/
34 schema:sdPublisher N6af19a7a6fbd46aea060dbfcd0fc55de
35 schema:url http://link.springer.com/10.1007/BF02025300
36 sgo:license sg:explorer/license/
37 sgo:sdDataset articles
38 rdf:type schema:ScholarlyArticle
39 N0ae3c401103f4a04858d0ceeff0b776f schema:name doi
40 schema:value 10.1007/bf02025300
41 rdf:type schema:PropertyValue
42 N4832045efafc407a92ef7a094cc162f5 schema:name readcube_id
43 schema:value 0ebd4dcd5eaccb43b56f02eea93301f4d5dba18738c0fff480a292d25137c9cb
44 rdf:type schema:PropertyValue
45 N6483f82cb19249f0aa9f275c9df16869 schema:name dimensions_id
46 schema:value pub.1003094219
47 rdf:type schema:PropertyValue
48 N6af19a7a6fbd46aea060dbfcd0fc55de schema:name Springer Nature - SN SciGraph project
49 rdf:type schema:Organization
50 N8dd3fe25bb244078b5a552ce198f8731 rdf:first sg:person.012600006066.78
51 rdf:rest rdf:nil
52 N957e4defb6c145faa8d11ce5f36a24ae rdf:first Nc4871fa2acf74dfab17eac6e7f83bc1d
53 rdf:rest N8dd3fe25bb244078b5a552ce198f8731
54 N9c5cef0d1ba1418ba29165cb8c6a8682 schema:issueNumber 5
55 rdf:type schema:PublicationIssue
56 Nbb83a2df2a31434babf14e36d0320382 schema:volumeNumber 43
57 rdf:type schema:PublicationVolume
58 Nc4871fa2acf74dfab17eac6e7f83bc1d schema:affiliation https://www.grid.ac/institutes/grid.6530.0
59 schema:familyName Kwatera
60 schema:givenName Renata Krystyna
61 rdf:type schema:Person
62 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
63 schema:name Mathematical Sciences
64 rdf:type schema:DefinedTerm
65 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
66 schema:name Numerical and Computational Mathematics
67 rdf:type schema:DefinedTerm
68 sg:journal.1048429 schema:issn 0254-5330
69 1572-9338
70 schema:name Annals of Operations Research
71 rdf:type schema:Periodical
72 sg:person.012600006066.78 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
73 schema:familyName Simeone
74 schema:givenName Bruno
75 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012600006066.78
76 rdf:type schema:Person
77 sg:pub.10.1007/bf01874392 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020540312
78 https://doi.org/10.1007/bf01874392
79 rdf:type schema:CreativeWork
80 sg:pub.10.1007/bfb0120886 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010250587
81 https://doi.org/10.1007/bfb0120886
82 rdf:type schema:CreativeWork
83 https://doi.org/10.1016/0167-6377(89)90002-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045066110
84 rdf:type schema:CreativeWork
85 https://doi.org/10.1016/0196-6774(81)90020-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022335295
86 rdf:type schema:CreativeWork
87 https://doi.org/10.1016/s0304-0208(08)73236-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032856118
88 rdf:type schema:CreativeWork
89 https://doi.org/10.1109/tpami.1980.4767027 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061741699
90 rdf:type schema:CreativeWork
91 https://doi.org/10.1137/0211045 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841661
92 rdf:type schema:CreativeWork
93 https://doi.org/10.1145/321958.321975 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048192025
94 rdf:type schema:CreativeWork
95 https://doi.org/10.1287/mnsc.25.4.329 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064719186
96 rdf:type schema:CreativeWork
97 https://doi.org/10.1287/moor.4.3.233 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064724457
98 rdf:type schema:CreativeWork
99 https://doi.org/10.1287/opre.23.1.74 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064728583
100 rdf:type schema:CreativeWork
101 https://doi.org/10.2307/2346439 schema:sameAs https://app.dimensions.ai/details/publication/pub.1101981384
102 rdf:type schema:CreativeWork
103 https://www.grid.ac/institutes/grid.6530.0 schema:alternateName University of Rome Tor Vergata
104 schema:name Dipartimento di Fisica, Università “Tor Vergata”, via della Ricerca Scientifica 1, 00173, Rome, Italy
105 rdf:type schema:Organization
106 https://www.grid.ac/institutes/grid.7841.a schema:alternateName Sapienza University of Rome
107 schema:name Dipartimento di Statistica, Probabilità e Statistiche Applicate, Università “La Sapienza”, Piazzale Aldo Moro 5, 00185, Rome, Italy
108 rdf:type schema:Organization
 




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


...