Collecting Weighted Items from a Dynamic Queue View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2011-10-04

AUTHORS

Marcin Bienkowski, Marek Chrobak, Christoph Dürr, Mathilde Hurand, Artur Jeż, Łukasz Jeż, Grzegorz Stachowiak

ABSTRACT

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 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... »

PAGES

60-94

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00453-011-9574-6

DOI

http://dx.doi.org/10.1007/s00453-011-9574-6

DIMENSIONS

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


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/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

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/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

Subject Predicate Object
1 sg:pub.10.1007/s00453-011-9574-6 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author N0e4d4dd7a47f420a9235e6de5d0ac66b
4 schema:citation sg:pub.10.1007/978-3-642-23719-5_21
5 sg:pub.10.1007/s00453-003-1025-6
6 sg:pub.10.1007/s00453-005-1158-x
7 schema:datePublished 2011-10-04
8 schema:datePublishedReg 2011-10-04
9 schema: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 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.
10 schema:genre article
11 schema:inLanguage en
12 schema:isAccessibleForFree true
13 schema:isPartOf Ncd509f966ad24c92afc224a801f45731
14 Ne83f9d03d0b547659636d24a71b86ebf
15 sg:journal.1047644
16 schema:keywords algorithm
17 arbitrary locations
18 bounds
19 cases
20 competitive algorithm
21 competitive ratio
22 consecutive time steps
23 content
24 dynamic queue
25 front
26 general case
27 generalization
28 items
29 location
30 lower bounds
31 number
32 number of items
33 objective
34 packet scheduling
35 problem
36 queue
37 ratio
38 restricted variants
39 s.
40 scheduling
41 step
42 time
43 time step
44 total weight
45 update
46 variants
47 varies
48 weight
49 weighted items
50 schema:name Collecting Weighted Items from a Dynamic Queue
51 schema:pagination 60-94
52 schema:productId N6c84c876b2a5407d9bbd00dfe89c1daf
53 N98eb6d47d1fa4495b64e8bb32eb4f0c1
54 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034026334
55 https://doi.org/10.1007/s00453-011-9574-6
56 schema:sdDatePublished 2022-06-01T22:11
57 schema:sdLicense https://scigraph.springernature.com/explorer/license/
58 schema:sdPublisher N106e1fd26f6f40018278981e6c8111be
59 schema:url https://doi.org/10.1007/s00453-011-9574-6
60 sgo:license sg:explorer/license/
61 sgo:sdDataset articles
62 rdf:type schema:ScholarlyArticle
63 N0a45bc6a91f945429e196d3ccb74e2e6 rdf:first sg:person.011733342103.27
64 rdf:rest Nffeb1ee5d7834f17a2ec2882f8b1840f
65 N0e4d4dd7a47f420a9235e6de5d0ac66b rdf:first sg:person.016246424337.74
66 rdf:rest N4150c4ff85364dbca12b826ed5eae741
67 N106e1fd26f6f40018278981e6c8111be schema:name Springer Nature - SN SciGraph project
68 rdf:type schema:Organization
69 N4150c4ff85364dbca12b826ed5eae741 rdf:first sg:person.07602333673.98
70 rdf:rest Nb3a0d6739848408f9922ff498bced418
71 N6c84c876b2a5407d9bbd00dfe89c1daf schema:name dimensions_id
72 schema:value pub.1034026334
73 rdf:type schema:PropertyValue
74 N98eb6d47d1fa4495b64e8bb32eb4f0c1 schema:name doi
75 schema:value 10.1007/s00453-011-9574-6
76 rdf:type schema:PropertyValue
77 Nb3a0d6739848408f9922ff498bced418 rdf:first sg:person.012155610373.98
78 rdf:rest N0a45bc6a91f945429e196d3ccb74e2e6
79 Ncd509f966ad24c92afc224a801f45731 schema:volumeNumber 65
80 rdf:type schema:PublicationVolume
81 Ncf1d5a3be06742818e647dc4a015c836 rdf:first sg:person.012551025031.36
82 rdf:rest rdf:nil
83 Ne83f9d03d0b547659636d24a71b86ebf schema:issueNumber 1
84 rdf:type schema:PublicationIssue
85 Necbf16f3ad0b4aef9b219da08938a66d rdf:first sg:person.011054455171.24
86 rdf:rest Ncf1d5a3be06742818e647dc4a015c836
87 Nffeb1ee5d7834f17a2ec2882f8b1840f rdf:first sg:person.015252371751.76
88 rdf:rest Necbf16f3ad0b4aef9b219da08938a66d
89 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
90 schema:name Information and Computing Sciences
91 rdf:type schema:DefinedTerm
92 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
93 schema:name Artificial Intelligence and Image Processing
94 rdf:type schema:DefinedTerm
95 sg:journal.1047644 schema:issn 0178-4617
96 1432-0541
97 schema:name Algorithmica
98 schema:publisher Springer Nature
99 rdf:type schema:Periodical
100 sg:person.011054455171.24 schema:affiliation grid-institutes:grid.8505.8
101 schema:familyName Jeż
102 schema:givenName Łukasz
103 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011054455171.24
104 rdf:type schema:Person
105 sg:person.011733342103.27 schema:affiliation grid-institutes:grid.472568.a
106 schema:familyName Hurand
107 schema:givenName Mathilde
108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011733342103.27
109 rdf:type schema:Person
110 sg:person.012155610373.98 schema:affiliation grid-institutes:grid.462751.3
111 schema:familyName Dürr
112 schema:givenName Christoph
113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012155610373.98
114 rdf:type schema:Person
115 sg:person.012551025031.36 schema:affiliation grid-institutes:grid.8505.8
116 schema:familyName Stachowiak
117 schema:givenName Grzegorz
118 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012551025031.36
119 rdf:type schema:Person
120 sg:person.015252371751.76 schema:affiliation grid-institutes:grid.8505.8
121 schema:familyName Jeż
122 schema:givenName Artur
123 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015252371751.76
124 rdf:type schema:Person
125 sg:person.016246424337.74 schema:affiliation grid-institutes:grid.8505.8
126 schema:familyName Bienkowski
127 schema:givenName Marcin
128 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016246424337.74
129 rdf:type schema:Person
130 sg:person.07602333673.98 schema:affiliation grid-institutes:grid.266097.c
131 schema:familyName Chrobak
132 schema:givenName Marek
133 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07602333673.98
134 rdf:type schema:Person
135 sg:pub.10.1007/978-3-642-23719-5_21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008629436
136 https://doi.org/10.1007/978-3-642-23719-5_21
137 rdf:type schema:CreativeWork
138 sg:pub.10.1007/s00453-003-1025-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011658478
139 https://doi.org/10.1007/s00453-003-1025-6
140 rdf:type schema:CreativeWork
141 sg:pub.10.1007/s00453-005-1158-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1033151527
142 https://doi.org/10.1007/s00453-005-1158-x
143 rdf:type schema:CreativeWork
144 grid-institutes:grid.266097.c schema:alternateName Department of Computer Science, University of California, 92521, Riverside, CA, USA
145 schema:name Department of Computer Science, University of California, 92521, Riverside, CA, USA
146 rdf:type schema:Organization
147 grid-institutes:grid.462751.3 schema:alternateName CNRS, LIP6, Université Pierre et Marie Curie, 75252, Paris Cedex 05, France
148 schema:name CNRS, LIP6, Université Pierre et Marie Curie, 75252, Paris Cedex 05, France
149 rdf:type schema:Organization
150 grid-institutes:grid.472568.a schema:alternateName Google, 8002, Zürich, Switzerland
151 schema:name Google, 8002, Zürich, Switzerland
152 rdf:type schema:Organization
153 grid-institutes:grid.8505.8 schema:alternateName Institute of Computer Science, University of Wrocław, 50-383, Wrocław, Poland
154 schema:name Institute of Computer Science, University of Wrocław, 50-383, Wrocław, Poland
155 rdf:type schema:Organization
 




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


...