On Randomized Online Labeling with Polynomially Many Labels View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2013

AUTHORS

Jan Bulánek , Michal Koucký , Michael Saks

ABSTRACT

We prove an optimal lower bound on the complexity of randomized algorithms for the online labeling problem with polynomially many labels. All previous work on this problem (both upper and lower bounds) only applied to deterministic algorithms, so this is the first paper addressing the (im)possibility of faster randomized algorithms. Our lower bound Ω(n log(n)) matches the complexity of a known deterministic algorithm for this setting of parameters so it is asymptotically optimal.In the online labeling problem with parameters n and m we are presented with a sequence of nitems from a totally ordered universe U and must assign each arriving item a label from the label set {1,2,…,m} so that the order of labels (strictly) respects the ordering on U. As new items arrive it may be necessary to change the labels of some items; such changes may be done at any time at unit cost for each change. The goal is to minimize the total cost. An alternative formulation of this problem is the file maintenance problem, in which the items, instead of being labeled, are maintained in sorted order in an array of length m, and we pay unit cost for moving an item. More... »

PAGES

291-302

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-39206-1_25

DOI

http://dx.doi.org/10.1007/978-3-642-39206-1_25

DIMENSIONS

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


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 Mathematics, Academy of Sciences CR, Prague, Czech Republic", 
          "id": "http://www.grid.ac/institutes/grid.425493.d", 
          "name": [
            "Department of Theoretical Computer Science and Mathematical Logic, Charles University, Prague, Czech Republic", 
            "Institute of Mathematics, Academy of Sciences CR, Prague, Czech Republic"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Bul\u00e1nek", 
        "givenName": "Jan", 
        "id": "sg:person.011527105643.50", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011527105643.50"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Institute of Mathematics, Academy of Sciences CR, Prague, Czech Republic", 
          "id": "http://www.grid.ac/institutes/grid.425493.d", 
          "name": [
            "Institute of Mathematics, Academy of Sciences CR, Prague, Czech Republic"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kouck\u00fd", 
        "givenName": "Michal", 
        "id": "sg:person.014077576120.58", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014077576120.58"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Mathematics, Rutgers University, USA", 
          "id": "http://www.grid.ac/institutes/grid.430387.b", 
          "name": [
            "Department of Mathematics, Rutgers University, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Saks", 
        "givenName": "Michael", 
        "id": "sg:person.011520224512.05", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2013", 
    "datePublishedReg": "2013-01-01", 
    "description": "We prove an optimal lower bound on the complexity of randomized algorithms for the online labeling problem with polynomially many labels. All previous work on this problem (both upper and lower bounds) only applied to deterministic algorithms, so this is the first paper addressing the (im)possibility of faster randomized algorithms. Our lower bound \u03a9(n log(n)) matches the complexity of a known deterministic algorithm for this setting of parameters so it is asymptotically optimal.In the online labeling problem with parameters n and m we are presented with a sequence of nitems from a totally ordered universe U and must assign each arriving item a label from the label set {1,2,\u2026,m} so that the order of labels (strictly) respects the ordering on U. As new items arrive it may be necessary to change the labels of some items; such changes may be done at any time at unit cost for each change. The goal is to minimize the total cost. An alternative formulation of this problem is the file maintenance problem, in which the items, instead of being labeled, are maintained in sorted order in an array of length m, and we pay unit cost for moving an item.", 
    "editor": [
      {
        "familyName": "Fomin", 
        "givenName": "Fedor V.", 
        "type": "Person"
      }, 
      {
        "familyName": "Freivalds", 
        "givenName": "R\u016bsi\u0146\u0161", 
        "type": "Person"
      }, 
      {
        "familyName": "Kwiatkowska", 
        "givenName": "Marta", 
        "type": "Person"
      }, 
      {
        "familyName": "Peleg", 
        "givenName": "David", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-39206-1_25", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-39205-4", 
        "978-3-642-39206-1"
      ], 
      "name": "Automata, Languages, and Programming", 
      "type": "Book"
    }, 
    "keywords": [
      "online labeling problem", 
      "labeling problem", 
      "deterministic algorithm", 
      "order of labels", 
      "file maintenance problem", 
      "setting of parameters", 
      "label set", 
      "online labeling", 
      "array of length", 
      "sorted order", 
      "algorithm", 
      "maintenance problems", 
      "universe U", 
      "labels", 
      "new items", 
      "complexity", 
      "previous work", 
      "cost", 
      "total cost", 
      "items", 
      "set", 
      "order", 
      "first paper", 
      "goal", 
      "work", 
      "unit cost", 
      "alternative formulation", 
      "time", 
      "sequence", 
      "setting", 
      "array", 
      "ordering", 
      "parameters", 
      "labeling", 
      "formulation", 
      "such changes", 
      "parameter n", 
      "changes", 
      "length", 
      "problem", 
      "paper"
    ], 
    "name": "On Randomized Online Labeling with Polynomially Many Labels", 
    "pagination": "291-302", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1004907289"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-39206-1_25"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-39206-1_25", 
      "https://app.dimensions.ai/details/publication/pub.1004907289"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-10-01T06:57", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221001/entities/gbq_results/chapter/chapter_370.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-39206-1_25"
  }
]
 

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-39206-1_25'

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-39206-1_25'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-39206-1_25'

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-39206-1_25'


 

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

133 TRIPLES      22 PREDICATES      66 URIs      59 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-39206-1_25 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author N0acf0f6c35594bb9b2dafdcf4e1d3cf5
4 schema:datePublished 2013
5 schema:datePublishedReg 2013-01-01
6 schema:description We prove an optimal lower bound on the complexity of randomized algorithms for the online labeling problem with polynomially many labels. All previous work on this problem (both upper and lower bounds) only applied to deterministic algorithms, so this is the first paper addressing the (im)possibility of faster randomized algorithms. Our lower bound Ω(n log(n)) matches the complexity of a known deterministic algorithm for this setting of parameters so it is asymptotically optimal.In the online labeling problem with parameters n and m we are presented with a sequence of nitems from a totally ordered universe U and must assign each arriving item a label from the label set {1,2,…,m} so that the order of labels (strictly) respects the ordering on U. As new items arrive it may be necessary to change the labels of some items; such changes may be done at any time at unit cost for each change. The goal is to minimize the total cost. An alternative formulation of this problem is the file maintenance problem, in which the items, instead of being labeled, are maintained in sorted order in an array of length m, and we pay unit cost for moving an item.
7 schema:editor N00ddd62857ad465794a0a6d195b13428
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf Nf4bb69a3e6b6490d980da41b7505ae7a
11 schema:keywords algorithm
12 alternative formulation
13 array
14 array of length
15 changes
16 complexity
17 cost
18 deterministic algorithm
19 file maintenance problem
20 first paper
21 formulation
22 goal
23 items
24 label set
25 labeling
26 labeling problem
27 labels
28 length
29 maintenance problems
30 new items
31 online labeling
32 online labeling problem
33 order
34 order of labels
35 ordering
36 paper
37 parameter n
38 parameters
39 previous work
40 problem
41 sequence
42 set
43 setting
44 setting of parameters
45 sorted order
46 such changes
47 time
48 total cost
49 unit cost
50 universe U
51 work
52 schema:name On Randomized Online Labeling with Polynomially Many Labels
53 schema:pagination 291-302
54 schema:productId N6754eb18d33e4bfe93a2c106891d43cc
55 Nfca299c9e2e241bd9babe32ade73ffd8
56 schema:publisher N82a94090ff234da7a505a44d65282e3c
57 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004907289
58 https://doi.org/10.1007/978-3-642-39206-1_25
59 schema:sdDatePublished 2022-10-01T06:57
60 schema:sdLicense https://scigraph.springernature.com/explorer/license/
61 schema:sdPublisher N8fa848789d0c4d25b15d020b82b942a5
62 schema:url https://doi.org/10.1007/978-3-642-39206-1_25
63 sgo:license sg:explorer/license/
64 sgo:sdDataset chapters
65 rdf:type schema:Chapter
66 N00ddd62857ad465794a0a6d195b13428 rdf:first N55a991153c8548009d0a36374a652093
67 rdf:rest Nedf472762fc74b368a66a7894bfcff4f
68 N0acf0f6c35594bb9b2dafdcf4e1d3cf5 rdf:first sg:person.011527105643.50
69 rdf:rest N48ab99d1dd4440dfa7299b391644736f
70 N205492e61838428dbff3afda6024aa1a schema:familyName Freivalds
71 schema:givenName Rūsiņš
72 rdf:type schema:Person
73 N35dbe72582e047fcbb5b72c92a3032da rdf:first sg:person.011520224512.05
74 rdf:rest rdf:nil
75 N48ab99d1dd4440dfa7299b391644736f rdf:first sg:person.014077576120.58
76 rdf:rest N35dbe72582e047fcbb5b72c92a3032da
77 N49557f9c53344cc0b31c488461ee5aef rdf:first N72e188090ca9468ea155500417e51291
78 rdf:rest rdf:nil
79 N55a991153c8548009d0a36374a652093 schema:familyName Fomin
80 schema:givenName Fedor V.
81 rdf:type schema:Person
82 N6754eb18d33e4bfe93a2c106891d43cc schema:name dimensions_id
83 schema:value pub.1004907289
84 rdf:type schema:PropertyValue
85 N72e188090ca9468ea155500417e51291 schema:familyName Peleg
86 schema:givenName David
87 rdf:type schema:Person
88 N735d0ad3b8854e2b87ac8f3d57e03a89 rdf:first Nc7a72dffd85c4d489b2d2a6526290407
89 rdf:rest N49557f9c53344cc0b31c488461ee5aef
90 N82a94090ff234da7a505a44d65282e3c schema:name Springer Nature
91 rdf:type schema:Organisation
92 N8fa848789d0c4d25b15d020b82b942a5 schema:name Springer Nature - SN SciGraph project
93 rdf:type schema:Organization
94 Nc7a72dffd85c4d489b2d2a6526290407 schema:familyName Kwiatkowska
95 schema:givenName Marta
96 rdf:type schema:Person
97 Nedf472762fc74b368a66a7894bfcff4f rdf:first N205492e61838428dbff3afda6024aa1a
98 rdf:rest N735d0ad3b8854e2b87ac8f3d57e03a89
99 Nf4bb69a3e6b6490d980da41b7505ae7a schema:isbn 978-3-642-39205-4
100 978-3-642-39206-1
101 schema:name Automata, Languages, and Programming
102 rdf:type schema:Book
103 Nfca299c9e2e241bd9babe32ade73ffd8 schema:name doi
104 schema:value 10.1007/978-3-642-39206-1_25
105 rdf:type schema:PropertyValue
106 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
107 schema:name Information and Computing Sciences
108 rdf:type schema:DefinedTerm
109 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
110 schema:name Artificial Intelligence and Image Processing
111 rdf:type schema:DefinedTerm
112 sg:person.011520224512.05 schema:affiliation grid-institutes:grid.430387.b
113 schema:familyName Saks
114 schema:givenName Michael
115 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05
116 rdf:type schema:Person
117 sg:person.011527105643.50 schema:affiliation grid-institutes:grid.425493.d
118 schema:familyName Bulánek
119 schema:givenName Jan
120 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011527105643.50
121 rdf:type schema:Person
122 sg:person.014077576120.58 schema:affiliation grid-institutes:grid.425493.d
123 schema:familyName Koucký
124 schema:givenName Michal
125 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014077576120.58
126 rdf:type schema:Person
127 grid-institutes:grid.425493.d schema:alternateName Institute of Mathematics, Academy of Sciences CR, Prague, Czech Republic
128 schema:name Department of Theoretical Computer Science and Mathematical Logic, Charles University, Prague, Czech Republic
129 Institute of Mathematics, Academy of Sciences CR, Prague, Czech Republic
130 rdf:type schema:Organization
131 grid-institutes:grid.430387.b schema:alternateName Department of Mathematics, Rutgers University, USA
132 schema:name Department of Mathematics, Rutgers University, USA
133 rdf:type schema:Organization
 




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


...