# Approximating the Online Set Multicover Problems via Randomized Winnowing

Ontology type: schema:Chapter      Open Access: True

### Chapter Info

DATE

2005

AUTHORS ABSTRACT

In this paper, we consider the weighted online set k- multicover problem. In this problem, we have an universe V of elements, a family \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{S}$\end{document} of subsets of V with a positive real cost for every \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$S \in \mathcal{S}$\end{document}, and a “coverage factor” (positive integer) k. A subset {i0, i1,...} ⊆ V of elements are presented online in an arbitrary order. When each element ip is presented, we are also told the collection of all (at least k) sets \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{S}_{i_p} \subseteq \mathcal{S}$\end{document} and their costs in which ip belongs and we need to select additional sets from \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{S}_{i_p}$\end{document} if necessary such that our collection of selected sets contains at leastk sets that contain the element ip. The goal is to minimize the total cost of the selected sets. In this paper, we describe a new randomized algorithm for the online multicover problem based on the randomized winnowing approach of [11]. This algorithm generalizes and improves some earlier results in [1]. We also discuss lower bounds on competitive ratios for deterministic algorithms for general k based on the approaches in [1]. More... »

PAGES

110-121

### Book

TITLE

Algorithms and Data Structures

ISBN

978-3-540-28101-6
978-3-540-31711-1

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11534273_11

DOI

http://dx.doi.org/10.1007/11534273_11

DIMENSIONS

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

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:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"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/0801",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Artificial Intelligence and Image Processing",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Department of Computer Science and Engineering, Pennsylvania State University, 16802, University Park, PA, USA",
"id": "http://www.grid.ac/institutes/grid.29857.31",
"name": [
"Department of Computer Science and Engineering, Pennsylvania State University, 16802, University Park, PA, USA"
],
"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": "Computer Science Department, University of Illinois at Chicago, 60607, Chicago, IL, USA",
"id": "http://www.grid.ac/institutes/grid.185648.6",
"name": [
"Computer Science Department, University of Illinois at Chicago, 60607, Chicago, IL, USA"
],
"type": "Organization"
},
"familyName": "DasGupta",
"id": "sg:person.0763403270.10",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0763403270.10"
],
"type": "Person"
}
],
"datePublished": "2005",
"datePublishedReg": "2005-01-01",
"description": "In this paper, we consider the weighted online set k- multicover problem. In this problem, we have an universe V of elements, a family \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\mathcal{S}$\\end{document} of subsets of V with a positive real cost for every \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$S \\in \\mathcal{S}$\\end{document}, and a \u201ccoverage factor\u201d (positive integer) k. A subset {i0, i1,...}\u2009\u2286\u2009V of elements are presented online in an arbitrary order. When each element ip is presented, we are also told the collection of all (at least k) sets \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\mathcal{S}_{i_p} \\subseteq \\mathcal{S}$\\end{document} and their costs in which ip belongs and we need to select additional sets from \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\mathcal{S}_{i_p}$\\end{document} if necessary such that our collection of selected sets contains at leastk sets that contain the element ip. The goal is to minimize the total cost of the selected sets. In this paper, we describe a new randomized algorithm for the online multicover problem based on the randomized winnowing approach of [11]. This algorithm generalizes and improves some earlier results in [1]. We also discuss lower bounds on competitive ratios for deterministic algorithms for general k based on the approaches in [1].",
"editor": [
{
"familyName": "Dehne",
"givenName": "Frank",
"type": "Person"
},
{
"familyName": "L\u00f3pez-Ortiz",
"givenName": "Alejandro",
"type": "Person"
},
{
"familyName": "Sack",
"givenName": "J\u00f6rg-R\u00fcdiger",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/11534273_11",
"inLanguage": "en",
"isAccessibleForFree": true,
"isPartOf": {
"isbn": [
"978-3-540-28101-6",
"978-3-540-31711-1"
],
"name": "Algorithms and Data Structures",
"type": "Book"
},
"keywords": [
"real cost",
"family",
"paper",
"approach",
"goal",
"collection",
"problem",
"elements",
"cost",
"set",
"order",
"factors",
"results",
"winnowing",
"IP",
"total cost",
"subset",
"earlier results",
"I1",
"bounds",
"ratio",
"competitive ratio",
"coverage factor",
"arbitrary order",
"algorithm",
"multicover problem",
"deterministic algorithm",
"set multicover problem",
"lower bounds",
"general k",
"set K",
"universe V",
"I0"
],
"name": "Approximating the Online Set Multicover Problems via Randomized Winnowing",
"pagination": "110-121",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1021364545"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/11534273_11"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/11534273_11",
"https://app.dimensions.ai/details/publication/pub.1021364545"
],
"sdDataset": "chapters",
"sdDatePublished": "2022-05-20T07:48",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_449.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/11534273_11"
}
]

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/11534273_11'

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/11534273_11'

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

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

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

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

114 TRIPLES      23 PREDICATES      60 URIs      53 LITERALS      7 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0801
3 schema:author N63a77fb735e54c5e81c23a072491b4fa
4 schema:datePublished 2005
5 schema:datePublishedReg 2005-01-01
6 schema:description In this paper, we consider the weighted online set k- multicover problem. In this problem, we have an universe V of elements, a family \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{S}$\end{document} of subsets of V with a positive real cost for every \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$S \in \mathcal{S}$\end{document}, and a “coverage factor” (positive integer) k. A subset {i0, i1,...} ⊆ V of elements are presented online in an arbitrary order. When each element ip is presented, we are also told the collection of all (at least k) sets \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{S}_{i_p} \subseteq \mathcal{S}$\end{document} and their costs in which ip belongs and we need to select additional sets from \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{S}_{i_p}$\end{document} if necessary such that our collection of selected sets contains at leastk sets that contain the element ip. The goal is to minimize the total cost of the selected sets. In this paper, we describe a new randomized algorithm for the online multicover problem based on the randomized winnowing approach of [11]. This algorithm generalizes and improves some earlier results in [1]. We also discuss lower bounds on competitive ratios for deterministic algorithms for general k based on the approaches in [1].
7 schema:editor N788b4301f9a941479fd5116f6f182af1
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N3cb1a21d854e42a6aaa1055f0b6850e1
12 schema:keywords I0
13 I1
14 IP
16 algorithm
17 approach
18 arbitrary order
19 bounds
20 collection
21 competitive ratio
22 cost
23 coverage factor
24 deterministic algorithm
25 earlier results
26 elements
27 factors
28 family
29 general k
30 goal
31 lower bounds
32 multicover problem
33 order
34 paper
35 problem
36 ratio
37 real cost
38 results
39 set
40 set K
41 set multicover problem
42 subset
43 total cost
44 universe V
45 winnowing
46 schema:name Approximating the Online Set Multicover Problems via Randomized Winnowing
47 schema:pagination 110-121
48 schema:productId N330f8b1c7d6844ff83969a167357da2a
49 N3e4ac982d2ef4ede96c8c940525c8927
50 schema:publisher Nc377d009c1d54a44a156e6fabe207c6f
51 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021364545
52 https://doi.org/10.1007/11534273_11
53 schema:sdDatePublished 2022-05-20T07:48
55 schema:sdPublisher N0ee82e80dc1a452faaa0eed4124ba62f
56 schema:url https://doi.org/10.1007/11534273_11
58 sgo:sdDataset chapters
59 rdf:type schema:Chapter
60 N0ee82e80dc1a452faaa0eed4124ba62f schema:name Springer Nature - SN SciGraph project
61 rdf:type schema:Organization
62 N1a650318b99a49ca87ff5c6e7e9f5f8d schema:familyName López-Ortiz
63 schema:givenName Alejandro
64 rdf:type schema:Person
65 N330f8b1c7d6844ff83969a167357da2a schema:name doi
66 schema:value 10.1007/11534273_11
67 rdf:type schema:PropertyValue
68 N3cb1a21d854e42a6aaa1055f0b6850e1 schema:isbn 978-3-540-28101-6
69 978-3-540-31711-1
70 schema:name Algorithms and Data Structures
71 rdf:type schema:Book
72 N3e4ac982d2ef4ede96c8c940525c8927 schema:name dimensions_id
73 schema:value pub.1021364545
74 rdf:type schema:PropertyValue
75 N5022954ab2f046ffaf77fe7696f96b9b rdf:first sg:person.0763403270.10
76 rdf:rest rdf:nil
77 N5cece222382547b6a1e4939456da004e schema:familyName Dehne
78 schema:givenName Frank
79 rdf:type schema:Person
80 N63a77fb735e54c5e81c23a072491b4fa rdf:first sg:person.01274506210.27
81 rdf:rest N5022954ab2f046ffaf77fe7696f96b9b
83 schema:givenName Jörg-Rüdiger
84 rdf:type schema:Person
85 N788b4301f9a941479fd5116f6f182af1 rdf:first N5cece222382547b6a1e4939456da004e
88 rdf:rest rdf:nil
90 rdf:rest N85745e1e87be4a4e8ff126c2a4c0e3fc
91 Nc377d009c1d54a44a156e6fabe207c6f schema:name Springer Nature
92 rdf:type schema:Organisation
93 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
94 schema:name Information and Computing Sciences
95 rdf:type schema:DefinedTerm
96 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
97 schema:name Artificial Intelligence and Image Processing
98 rdf:type schema:DefinedTerm
99 sg:person.01274506210.27 schema:affiliation grid-institutes:grid.29857.31
100 schema:familyName Berman
101 schema:givenName Piotr
102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27
103 rdf:type schema:Person
104 sg:person.0763403270.10 schema:affiliation grid-institutes:grid.185648.6
105 schema:familyName DasGupta
107 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0763403270.10
108 rdf:type schema:Person
109 grid-institutes:grid.185648.6 schema:alternateName Computer Science Department, University of Illinois at Chicago, 60607, Chicago, IL, USA
110 schema:name Computer Science Department, University of Illinois at Chicago, 60607, Chicago, IL, USA
111 rdf:type schema:Organization
112 grid-institutes:grid.29857.31 schema:alternateName Department of Computer Science and Engineering, Pennsylvania State University, 16802, University Park, PA, USA
113 schema:name Department of Computer Science and Engineering, Pennsylvania State University, 16802, University Park, PA, USA
114 rdf:type schema:Organization