A linear programming based heuristic for a hard clustering problem on trees View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1998

AUTHORS

Isabella Lari , Maurizio Maravalle , Bruno Simeone

ABSTRACT

Clustering problems with relational constraints in which the underlying graph is a tree arise in a variety of applications: hierarchical data base paging, communication and distribution network districting, biological taxonomy, and others. They are formulated here as optimal tree partitioning problems. In a previous paper, it was shown that their computational complexity strongly depends on the nature of the objective function and, in particular, that minimizing the total within-cluster dissimilarity or the diameter is computationally hard. We propose a heuristic which finds good partitions for the first problem within a reasonable time, even when its size is large. Such heuristic is based on the solution of a linear program and a maximal network flow one, and in any case it yields an explicit estimate of the relative approximation error. With minor variations a similar approach yields good solutions for the minimum diameter problem. More... »

PAGES

161-170

References to SciGraph publications

Book

TITLE

Advances in Data Science and Classification

ISBN

978-3-540-64641-9
978-3-642-72253-0

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-72253-0_22

DOI

http://dx.doi.org/10.1007/978-3-642-72253-0_22

DIMENSIONS

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


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "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": "Sapienza University of Rome", 
          "id": "https://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "Department of Statistics, \u201cLa Sapienza\u201d University, P.le A. Moro 5, 00185\u00a0Rome, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lari", 
        "givenName": "Isabella", 
        "id": "sg:person.014622102543.45", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014622102543.45"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of L'Aquila", 
          "id": "https://www.grid.ac/institutes/grid.158820.6", 
          "name": [
            "Department of Systems for Economics, University of L\u2019Aquila, Via Assergi, 6, 67100\u00a0L\u2019Aquila, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Maravalle", 
        "givenName": "Maurizio", 
        "id": "sg:person.01171206147.24", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01171206147.24"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Sapienza University of Rome", 
          "id": "https://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "Department of Statistics, \u201cLa Sapienza\u201d University, P.le A. Moro 5, 00185\u00a0Rome, 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/bf02293706", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1001739880", 
          "https://doi.org/10.1007/bf02293706"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/comjnl/28.1.82", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019570203"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0167-9473(96)00062-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049632666"
        ], 
        "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.1287/mnsc.22.11.1268", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064718586"
        ], 
        "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/opre.34.2.250", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064729706"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.2307/2530494", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1069975999"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1998", 
    "datePublishedReg": "1998-01-01", 
    "description": "Clustering problems with relational constraints in which the underlying graph is a tree arise in a variety of applications: hierarchical data base paging, communication and distribution network districting, biological taxonomy, and others. They are formulated here as optimal tree partitioning problems. In a previous paper, it was shown that their computational complexity strongly depends on the nature of the objective function and, in particular, that minimizing the total within-cluster dissimilarity or the diameter is computationally hard. We propose a heuristic which finds good partitions for the first problem within a reasonable time, even when its size is large. Such heuristic is based on the solution of a linear program and a maximal network flow one, and in any case it yields an explicit estimate of the relative approximation error. With minor variations a similar approach yields good solutions for the minimum diameter problem.", 
    "editor": [
      {
        "familyName": "Rizzi", 
        "givenName": "Alfredo", 
        "type": "Person"
      }, 
      {
        "familyName": "Vichi", 
        "givenName": "Maurizio", 
        "type": "Person"
      }, 
      {
        "familyName": "Bock", 
        "givenName": "Hans-Hermann", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-72253-0_22", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-64641-9", 
        "978-3-642-72253-0"
      ], 
      "name": "Advances in Data Science and Classification", 
      "type": "Book"
    }, 
    "name": "A linear programming based heuristic for a hard clustering problem on trees", 
    "pagination": "161-170", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-72253-0_22"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "eec2f62309fd1e980d2c5a52e3117079e7778ef83501ec694fb917374ca6177f"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1050120962"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-72253-0_22", 
      "https://app.dimensions.ai/details/publication/pub.1050120962"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T18: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_8681_00000274.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/978-3-642-72253-0_22"
  }
]
 

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/978-3-642-72253-0_22'

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/978-3-642-72253-0_22'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-72253-0_22'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-72253-0_22'


 

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

117 TRIPLES      23 PREDICATES      35 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-72253-0_22 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N672f3db5bf5548cfbe5034747ac9154f
4 schema:citation sg:pub.10.1007/bf02293706
5 https://doi.org/10.1016/s0167-9473(96)00062-x
6 https://doi.org/10.1093/comjnl/28.1.82
7 https://doi.org/10.1109/tpami.1980.4767027
8 https://doi.org/10.1287/mnsc.22.11.1268
9 https://doi.org/10.1287/mnsc.25.4.329
10 https://doi.org/10.1287/opre.34.2.250
11 https://doi.org/10.2307/2530494
12 schema:datePublished 1998
13 schema:datePublishedReg 1998-01-01
14 schema:description Clustering problems with relational constraints in which the underlying graph is a tree arise in a variety of applications: hierarchical data base paging, communication and distribution network districting, biological taxonomy, and others. They are formulated here as optimal tree partitioning problems. In a previous paper, it was shown that their computational complexity strongly depends on the nature of the objective function and, in particular, that minimizing the total within-cluster dissimilarity or the diameter is computationally hard. We propose a heuristic which finds good partitions for the first problem within a reasonable time, even when its size is large. Such heuristic is based on the solution of a linear program and a maximal network flow one, and in any case it yields an explicit estimate of the relative approximation error. With minor variations a similar approach yields good solutions for the minimum diameter problem.
15 schema:editor N3c887df5733b4816b18a5bc9ab3c321b
16 schema:genre chapter
17 schema:inLanguage en
18 schema:isAccessibleForFree false
19 schema:isPartOf N73f7a4490e67494b94606bb0057f38e6
20 schema:name A linear programming based heuristic for a hard clustering problem on trees
21 schema:pagination 161-170
22 schema:productId N22afbac5920949b4a91bb74fa38ebb9a
23 N83444fd8e7a44e00b3a860e18622dda2
24 Na989631875ff471d9b561a11cb3dc696
25 schema:publisher N9643d25ce4df494ea4d9e550df5288ae
26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050120962
27 https://doi.org/10.1007/978-3-642-72253-0_22
28 schema:sdDatePublished 2019-04-15T18:14
29 schema:sdLicense https://scigraph.springernature.com/explorer/license/
30 schema:sdPublisher N4c08f59d6ed242ceabda73fb71bc9ea0
31 schema:url http://link.springer.com/10.1007/978-3-642-72253-0_22
32 sgo:license sg:explorer/license/
33 sgo:sdDataset chapters
34 rdf:type schema:Chapter
35 N22afbac5920949b4a91bb74fa38ebb9a schema:name readcube_id
36 schema:value eec2f62309fd1e980d2c5a52e3117079e7778ef83501ec694fb917374ca6177f
37 rdf:type schema:PropertyValue
38 N2850f447265a417a97f7cec3482fdc5e rdf:first N74a9e1c1fa054132936d36a2c3d1485b
39 rdf:rest Na2f978cac6d749b2ac9d179ba5587576
40 N3c887df5733b4816b18a5bc9ab3c321b rdf:first N911e4b80f5ee49d69117a969e110a086
41 rdf:rest N2850f447265a417a97f7cec3482fdc5e
42 N4c08f59d6ed242ceabda73fb71bc9ea0 schema:name Springer Nature - SN SciGraph project
43 rdf:type schema:Organization
44 N610e90608de04ae282ceffccae4b08ab schema:familyName Bock
45 schema:givenName Hans-Hermann
46 rdf:type schema:Person
47 N672f3db5bf5548cfbe5034747ac9154f rdf:first sg:person.014622102543.45
48 rdf:rest N77f6f405d1604494aebb3339b5149c5b
49 N73f7a4490e67494b94606bb0057f38e6 schema:isbn 978-3-540-64641-9
50 978-3-642-72253-0
51 schema:name Advances in Data Science and Classification
52 rdf:type schema:Book
53 N74a9e1c1fa054132936d36a2c3d1485b schema:familyName Vichi
54 schema:givenName Maurizio
55 rdf:type schema:Person
56 N77f6f405d1604494aebb3339b5149c5b rdf:first sg:person.01171206147.24
57 rdf:rest N9f63017d9d9c449383c53cddc4b663ae
58 N83444fd8e7a44e00b3a860e18622dda2 schema:name dimensions_id
59 schema:value pub.1050120962
60 rdf:type schema:PropertyValue
61 N911e4b80f5ee49d69117a969e110a086 schema:familyName Rizzi
62 schema:givenName Alfredo
63 rdf:type schema:Person
64 N9643d25ce4df494ea4d9e550df5288ae schema:location Berlin, Heidelberg
65 schema:name Springer Berlin Heidelberg
66 rdf:type schema:Organisation
67 N9f63017d9d9c449383c53cddc4b663ae rdf:first sg:person.012600006066.78
68 rdf:rest rdf:nil
69 Na2f978cac6d749b2ac9d179ba5587576 rdf:first N610e90608de04ae282ceffccae4b08ab
70 rdf:rest rdf:nil
71 Na989631875ff471d9b561a11cb3dc696 schema:name doi
72 schema:value 10.1007/978-3-642-72253-0_22
73 rdf:type schema:PropertyValue
74 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
75 schema:name Information and Computing Sciences
76 rdf:type schema:DefinedTerm
77 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
78 schema:name Computation Theory and Mathematics
79 rdf:type schema:DefinedTerm
80 sg:person.01171206147.24 schema:affiliation https://www.grid.ac/institutes/grid.158820.6
81 schema:familyName Maravalle
82 schema:givenName Maurizio
83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01171206147.24
84 rdf:type schema:Person
85 sg:person.012600006066.78 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
86 schema:familyName Simeone
87 schema:givenName Bruno
88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012600006066.78
89 rdf:type schema:Person
90 sg:person.014622102543.45 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
91 schema:familyName Lari
92 schema:givenName Isabella
93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014622102543.45
94 rdf:type schema:Person
95 sg:pub.10.1007/bf02293706 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001739880
96 https://doi.org/10.1007/bf02293706
97 rdf:type schema:CreativeWork
98 https://doi.org/10.1016/s0167-9473(96)00062-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1049632666
99 rdf:type schema:CreativeWork
100 https://doi.org/10.1093/comjnl/28.1.82 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019570203
101 rdf:type schema:CreativeWork
102 https://doi.org/10.1109/tpami.1980.4767027 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061741699
103 rdf:type schema:CreativeWork
104 https://doi.org/10.1287/mnsc.22.11.1268 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064718586
105 rdf:type schema:CreativeWork
106 https://doi.org/10.1287/mnsc.25.4.329 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064719186
107 rdf:type schema:CreativeWork
108 https://doi.org/10.1287/opre.34.2.250 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064729706
109 rdf:type schema:CreativeWork
110 https://doi.org/10.2307/2530494 schema:sameAs https://app.dimensions.ai/details/publication/pub.1069975999
111 rdf:type schema:CreativeWork
112 https://www.grid.ac/institutes/grid.158820.6 schema:alternateName University of L'Aquila
113 schema:name Department of Systems for Economics, University of L’Aquila, Via Assergi, 6, 67100 L’Aquila, Italy
114 rdf:type schema:Organization
115 https://www.grid.ac/institutes/grid.7841.a schema:alternateName Sapienza University of Rome
116 schema:name Department of Statistics, “La Sapienza” University, P.le A. Moro 5, 00185 Rome, Italy
117 rdf:type schema:Organization
 




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


...