Ontology type: schema:ScholarlyArticle Open Access: True
2011-10-04
AUTHORSMarcin Bienkowski, Marek Chrobak, Christoph Dürr, Mathilde Hurand, Artur Jeż, Łukasz Jeż, Grzegorz Stachowiak
ABSTRACTWe consider online competitive algorithms for the problem of collecting weighted items from a dynamic queue S. The content of S varies over time. An update to S can occur between any two consecutive time steps, and it consists in deleting any number of items at the front of S and inserting other items into arbitrary locations in S. At each time step we are allowed to collect one item in S. The objective is to maximize the total weight of collected items. This is a generalization of bounded-delay packet scheduling (also known as buffer management). We present several upper and lower bounds on the competitive ratio for the general case and for some restricted variants of this problem. More... »
PAGES60-94
http://scigraph.springernature.com/pub.10.1007/s00453-011-9574-6
DOIhttp://dx.doi.org/10.1007/s00453-011-9574-6
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1034026334
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/0801",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Artificial Intelligence and Image Processing",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Institute of Computer Science, University of Wroc\u0142aw, 50-383, Wroc\u0142aw, Poland",
"id": "http://www.grid.ac/institutes/grid.8505.8",
"name": [
"Institute of Computer Science, University of Wroc\u0142aw, 50-383, Wroc\u0142aw, Poland"
],
"type": "Organization"
},
"familyName": "Bienkowski",
"givenName": "Marcin",
"id": "sg:person.016246424337.74",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016246424337.74"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Computer Science, University of California, 92521, Riverside, CA, USA",
"id": "http://www.grid.ac/institutes/grid.266097.c",
"name": [
"Department of Computer Science, University of California, 92521, Riverside, CA, USA"
],
"type": "Organization"
},
"familyName": "Chrobak",
"givenName": "Marek",
"id": "sg:person.07602333673.98",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07602333673.98"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "CNRS, LIP6, Universit\u00e9 Pierre et Marie Curie, 75252, Paris Cedex 05, France",
"id": "http://www.grid.ac/institutes/grid.462751.3",
"name": [
"CNRS, LIP6, Universit\u00e9 Pierre et Marie Curie, 75252, Paris Cedex 05, France"
],
"type": "Organization"
},
"familyName": "D\u00fcrr",
"givenName": "Christoph",
"id": "sg:person.012155610373.98",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012155610373.98"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Google, 8002, Z\u00fcrich, Switzerland",
"id": "http://www.grid.ac/institutes/grid.472568.a",
"name": [
"Google, 8002, Z\u00fcrich, Switzerland"
],
"type": "Organization"
},
"familyName": "Hurand",
"givenName": "Mathilde",
"id": "sg:person.011733342103.27",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011733342103.27"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Institute of Computer Science, University of Wroc\u0142aw, 50-383, Wroc\u0142aw, Poland",
"id": "http://www.grid.ac/institutes/grid.8505.8",
"name": [
"Institute of Computer Science, University of Wroc\u0142aw, 50-383, Wroc\u0142aw, Poland"
],
"type": "Organization"
},
"familyName": "Je\u017c",
"givenName": "Artur",
"id": "sg:person.015252371751.76",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015252371751.76"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Institute of Computer Science, University of Wroc\u0142aw, 50-383, Wroc\u0142aw, Poland",
"id": "http://www.grid.ac/institutes/grid.8505.8",
"name": [
"Institute of Computer Science, University of Wroc\u0142aw, 50-383, Wroc\u0142aw, Poland"
],
"type": "Organization"
},
"familyName": "Je\u017c",
"givenName": "\u0141ukasz",
"id": "sg:person.011054455171.24",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011054455171.24"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Institute of Computer Science, University of Wroc\u0142aw, 50-383, Wroc\u0142aw, Poland",
"id": "http://www.grid.ac/institutes/grid.8505.8",
"name": [
"Institute of Computer Science, University of Wroc\u0142aw, 50-383, Wroc\u0142aw, Poland"
],
"type": "Organization"
},
"familyName": "Stachowiak",
"givenName": "Grzegorz",
"id": "sg:person.012551025031.36",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012551025031.36"
],
"type": "Person"
}
],
"citation": [
{
"id": "sg:pub.10.1007/s00453-005-1158-x",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1033151527",
"https://doi.org/10.1007/s00453-005-1158-x"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-23719-5_21",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1008629436",
"https://doi.org/10.1007/978-3-642-23719-5_21"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s00453-003-1025-6",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1011658478",
"https://doi.org/10.1007/s00453-003-1025-6"
],
"type": "CreativeWork"
}
],
"datePublished": "2011-10-04",
"datePublishedReg": "2011-10-04",
"description": "We consider online competitive algorithms for the problem of collecting weighted items from a dynamic queue S. The content of S varies over time. An update to S can occur between any two consecutive time steps, and it consists in deleting any number of items at the front of S and inserting other items into arbitrary locations in\u00a0S. At each time step we are allowed to collect one item in S. The objective is to maximize the total weight of collected items. This is a generalization of bounded-delay packet scheduling (also known as buffer management). We present several upper and lower bounds on the competitive ratio for the general case and for some restricted variants of this problem.",
"genre": "article",
"id": "sg:pub.10.1007/s00453-011-9574-6",
"inLanguage": "en",
"isAccessibleForFree": true,
"isPartOf": [
{
"id": "sg:journal.1047644",
"issn": [
"0178-4617",
"1432-0541"
],
"name": "Algorithmica",
"publisher": "Springer Nature",
"type": "Periodical"
},
{
"issueNumber": "1",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
"volumeNumber": "65"
}
],
"keywords": [
"weighted items",
"consecutive time steps",
"packet scheduling",
"dynamic queue",
"competitive algorithm",
"competitive ratio",
"time step",
"restricted variants",
"arbitrary locations",
"lower bounds",
"general case",
"number of items",
"scheduling",
"algorithm",
"queue",
"items",
"update",
"step",
"problem",
"bounds",
"generalization",
"location",
"number",
"time",
"objective",
"total weight",
"variants",
"front",
"content",
"cases",
"weight",
"ratio",
"s.",
"varies"
],
"name": "Collecting Weighted Items from a Dynamic Queue",
"pagination": "60-94",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1034026334"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/s00453-011-9574-6"
]
}
],
"sameAs": [
"https://doi.org/10.1007/s00453-011-9574-6",
"https://app.dimensions.ai/details/publication/pub.1034026334"
],
"sdDataset": "articles",
"sdDatePublished": "2022-06-01T22:11",
"sdLicense": "https://scigraph.springernature.com/explorer/license/",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220601/entities/gbq_results/article/article_542.jsonl",
"type": "ScholarlyArticle",
"url": "https://doi.org/10.1007/s00453-011-9574-6"
}
]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/s00453-011-9574-6'
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/s00453-011-9574-6'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-011-9574-6'
RDF/XML is a standard XML format for linked data.
curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-011-9574-6'
This table displays all metadata directly associated to this object as RDF triples.
155 TRIPLES
22 PREDICATES
62 URIs
51 LITERALS
6 BLANK NODES