Ontology type: schema:Chapter
2010
AUTHORSPiotr Berman , Sofya Raskhodnikova
ABSTRACTWe 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... »
PAGES53-66
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
ISBN
978-3-642-15368-6
978-3-642-15369-3
http://scigraph.springernature.com/pub.10.1007/978-3-642-15369-3_5
DOIhttp://dx.doi.org/10.1007/978-3-642-15369-3_5
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1053251447
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
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 |