Approximation Algorithms for Min-Max Generalization Problems View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2010

AUTHORS

Piotr Berman , Sofya Raskhodnikova

ABSTRACT

We provide improved approximation algorithms for the min-max generalization problems considered by Du, Eppstein, Goodrich, and Lueker [1]. In min-max generalization problems, the input consists of data items with weights and a lower bound wlb, and the goal is to partition individual items into groups of weight at least wlb, while minimizing the maximum weight of a group. The rules of legal partitioning are specific to a problem. Du et al. consider several problems in this vein: (1) partitioning a graph into connected subgraphs, (2) partitioning unstructured data into arbitrary classes and (3) partitioning a 2-dimensional array into non-overlapping contiguous rectangles (subarrays) that satisfy the above size requirements.We significantly improve approximation ratios for all the problems considered by Du et al., and provide additional motivation for these problems. Moreover, for the first problem, while Du et al. give approximation algorithms for specific graph families, namely, 3-connected and 4-connected planar graphs, no approximation algorithm that works for all graphs was known prior to this work. More... »

PAGES

53-66

Book

TITLE

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

ISBN

978-3-642-15368-6
978-3-642-15369-3

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-15369-3_5

DOI

http://dx.doi.org/10.1007/978-3-642-15369-3_5

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Pennsylvania State University", 
          "id": "http://www.grid.ac/institutes/grid.29857.31", 
          "name": [
            "Pennsylvania State University"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Berman", 
        "givenName": "Piotr", 
        "id": "sg:person.01274506210.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Pennsylvania State University", 
          "id": "http://www.grid.ac/institutes/grid.29857.31", 
          "name": [
            "Pennsylvania State University"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Raskhodnikova", 
        "givenName": "Sofya", 
        "id": "sg:person.07502404747.45", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07502404747.45"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2010", 
    "datePublishedReg": "2010-01-01", 
    "description": "We provide improved approximation algorithms for the min-max generalization problems considered by Du, Eppstein, Goodrich, and Lueker\u00a0[1]. In min-max generalization problems, the input consists of data items with weights and a lower bound wlb, and the goal is to partition individual items into groups of weight at least wlb, while minimizing the maximum weight of a group. The rules of legal partitioning are specific to a problem. Du\u00a0et al. consider several problems in this vein: (1) partitioning a graph into connected subgraphs, (2)\u00a0partitioning unstructured data into arbitrary classes and (3) partitioning a 2-dimensional array into non-overlapping contiguous rectangles (subarrays) that satisfy the above size requirements.We significantly improve approximation ratios for all the problems considered by Du\u00a0et al., and provide additional motivation for these problems. Moreover, for the first problem, while Du\u00a0et al. give approximation algorithms for specific graph families, namely, 3-connected and 4-connected planar graphs, no approximation algorithm that works for all graphs was known prior to this work.", 
    "editor": [
      {
        "familyName": "Serna", 
        "givenName": "Maria", 
        "type": "Person"
      }, 
      {
        "familyName": "Shaltiel", 
        "givenName": "Ronen", 
        "type": "Person"
      }, 
      {
        "familyName": "Jansen", 
        "givenName": "Klaus", 
        "type": "Person"
      }, 
      {
        "familyName": "Rolim", 
        "givenName": "Jos\u00e9", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-15369-3_5", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-15368-6", 
        "978-3-642-15369-3"
      ], 
      "name": "Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques", 
      "type": "Book"
    }, 
    "keywords": [
      "generalization problem", 
      "approximation algorithm", 
      "specific graph families", 
      "unstructured data", 
      "data items", 
      "group of weights", 
      "improved approximation algorithms", 
      "approximation ratio", 
      "connected subgraph", 
      "algorithm", 
      "graph families", 
      "graph", 
      "first problem", 
      "planar graphs", 
      "arbitrary class", 
      "maximum weight", 
      "Lueker", 
      "subgraphs", 
      "Eppstein", 
      "size requirements", 
      "requirements", 
      "additional motivation", 
      "rules", 
      "rectangle", 
      "items", 
      "partitioning", 
      "input", 
      "goal", 
      "et al", 
      "individual items", 
      "work", 
      "data", 
      "class", 
      "motivation", 
      "array", 
      "weight", 
      "al", 
      "Goodrich", 
      "WLB", 
      "problem", 
      "DU", 
      "group", 
      "ratio", 
      "family", 
      "vein"
    ], 
    "name": "Approximation Algorithms for Min-Max Generalization Problems", 
    "pagination": "53-66", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1053251447"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-15369-3_5"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-15369-3_5", 
      "https://app.dimensions.ai/details/publication/pub.1053251447"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-08-04T17:20", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220804/entities/gbq_results/chapter/chapter_402.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-15369-3_5"
  }
]
 

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-15369-3_5'

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-15369-3_5'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-15369-3_5'

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-15369-3_5'


 

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

126 TRIPLES      22 PREDICATES      70 URIs      63 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-15369-3_5 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N849fdc2e51394f6c84e7daf2dd5e867b
4 schema:datePublished 2010
5 schema:datePublishedReg 2010-01-01
6 schema:description We provide improved approximation algorithms for the min-max generalization problems considered by Du, Eppstein, Goodrich, and Lueker [1]. In min-max generalization problems, the input consists of data items with weights and a lower bound wlb, and the goal is to partition individual items into groups of weight at least wlb, while minimizing the maximum weight of a group. The rules of legal partitioning are specific to a problem. Du et al. consider several problems in this vein: (1) partitioning a graph into connected subgraphs, (2) partitioning unstructured data into arbitrary classes and (3) partitioning a 2-dimensional array into non-overlapping contiguous rectangles (subarrays) that satisfy the above size requirements.We significantly improve approximation ratios for all the problems considered by Du et al., and provide additional motivation for these problems. Moreover, for the first problem, while Du et al. give approximation algorithms for specific graph families, namely, 3-connected and 4-connected planar graphs, no approximation algorithm that works for all graphs was known prior to this work.
7 schema:editor Ne193416ce36d454ebaac1e917c5cae68
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N4ea0dcbe962c42e9aafb5853e30ce267
11 schema:keywords DU
12 Eppstein
13 Goodrich
14 Lueker
15 WLB
16 additional motivation
17 al
18 algorithm
19 approximation algorithm
20 approximation ratio
21 arbitrary class
22 array
23 class
24 connected subgraph
25 data
26 data items
27 et al
28 family
29 first problem
30 generalization problem
31 goal
32 graph
33 graph families
34 group
35 group of weights
36 improved approximation algorithms
37 individual items
38 input
39 items
40 maximum weight
41 motivation
42 partitioning
43 planar graphs
44 problem
45 ratio
46 rectangle
47 requirements
48 rules
49 size requirements
50 specific graph families
51 subgraphs
52 unstructured data
53 vein
54 weight
55 work
56 schema:name Approximation Algorithms for Min-Max Generalization Problems
57 schema:pagination 53-66
58 schema:productId N44d511db998a4490a5947ccaf97cbbd1
59 N68561b52b1c44377a3b29bbacf51f76e
60 schema:publisher Nc98863a9348c4dd0b1e42e666d32184d
61 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053251447
62 https://doi.org/10.1007/978-3-642-15369-3_5
63 schema:sdDatePublished 2022-08-04T17:20
64 schema:sdLicense https://scigraph.springernature.com/explorer/license/
65 schema:sdPublisher Nb093420efaf14c4bb1670d65c82b9966
66 schema:url https://doi.org/10.1007/978-3-642-15369-3_5
67 sgo:license sg:explorer/license/
68 sgo:sdDataset chapters
69 rdf:type schema:Chapter
70 N0e645add2df24034baca36506f683aab rdf:first sg:person.07502404747.45
71 rdf:rest rdf:nil
72 N1db3f108d98f4e3bba8f1a49f77dad39 rdf:first N555185bcf12441a38c1d0024ef0a8baf
73 rdf:rest Nf487d657a8104a1aa62b1bd4e5a552b5
74 N44d511db998a4490a5947ccaf97cbbd1 schema:name dimensions_id
75 schema:value pub.1053251447
76 rdf:type schema:PropertyValue
77 N4ea0dcbe962c42e9aafb5853e30ce267 schema:isbn 978-3-642-15368-6
78 978-3-642-15369-3
79 schema:name Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
80 rdf:type schema:Book
81 N555185bcf12441a38c1d0024ef0a8baf schema:familyName Jansen
82 schema:givenName Klaus
83 rdf:type schema:Person
84 N68561b52b1c44377a3b29bbacf51f76e schema:name doi
85 schema:value 10.1007/978-3-642-15369-3_5
86 rdf:type schema:PropertyValue
87 N6cffe9dee26e4e33abe6ed7bc11c10fa rdf:first N7c5ac924b1ba44b79655f86393429206
88 rdf:rest N1db3f108d98f4e3bba8f1a49f77dad39
89 N7c5ac924b1ba44b79655f86393429206 schema:familyName Shaltiel
90 schema:givenName Ronen
91 rdf:type schema:Person
92 N849fdc2e51394f6c84e7daf2dd5e867b rdf:first sg:person.01274506210.27
93 rdf:rest N0e645add2df24034baca36506f683aab
94 Nb093420efaf14c4bb1670d65c82b9966 schema:name Springer Nature - SN SciGraph project
95 rdf:type schema:Organization
96 Nbeb5b47f3ea844328b3a7e3aed172bb1 schema:familyName Rolim
97 schema:givenName José
98 rdf:type schema:Person
99 Nc98863a9348c4dd0b1e42e666d32184d schema:name Springer Nature
100 rdf:type schema:Organisation
101 Ne193416ce36d454ebaac1e917c5cae68 rdf:first Nfc7a173411754172ab4075e4671f9857
102 rdf:rest N6cffe9dee26e4e33abe6ed7bc11c10fa
103 Nf487d657a8104a1aa62b1bd4e5a552b5 rdf:first Nbeb5b47f3ea844328b3a7e3aed172bb1
104 rdf:rest rdf:nil
105 Nfc7a173411754172ab4075e4671f9857 schema:familyName Serna
106 schema:givenName Maria
107 rdf:type schema:Person
108 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
109 schema:name Information and Computing Sciences
110 rdf:type schema:DefinedTerm
111 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
112 schema:name Computation Theory and Mathematics
113 rdf:type schema:DefinedTerm
114 sg:person.01274506210.27 schema:affiliation grid-institutes:grid.29857.31
115 schema:familyName Berman
116 schema:givenName Piotr
117 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27
118 rdf:type schema:Person
119 sg:person.07502404747.45 schema:affiliation grid-institutes:grid.29857.31
120 schema:familyName Raskhodnikova
121 schema:givenName Sofya
122 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07502404747.45
123 rdf:type schema:Person
124 grid-institutes:grid.29857.31 schema:alternateName Pennsylvania State University
125 schema:name Pennsylvania State University
126 rdf:type schema:Organization
 




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


...