Online Labeling: Algorithms, Lower Bounds and Open Questions View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2018-04-25

AUTHORS

Michael Saks

ABSTRACT

The online labeling problem (also known as the file maintenance problem), is a natural algorithmic problem that has arisen as a buidling block for data structures. A stream of distinct integer items is to be assigned labels online from a label set \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\{1,\ldots ,m\}$$\end{document} so that the order of the labels respects the natural order of the items. Maintaining order on the labels may require relabeling items. The algorithm pays 1 each time an item is labeled or relabeled and the goal of the algorithm is to minimize the total cost.We survey upper and lower bounds and open problems in both the deterministic and randomized setting. More... »

PAGES

23-28

Book

TITLE

Computer Science – Theory and Applications

ISBN

978-3-319-90529-7
978-3-319-90530-3

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-90530-3_3

DOI

http://dx.doi.org/10.1007/978-3-319-90530-3_3

DIMENSIONS

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


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": "Department of Mathematics, Rutgers University, 08854, New Brunswick, NJ, USA", 
          "id": "http://www.grid.ac/institutes/grid.430387.b", 
          "name": [
            "Department of Mathematics, Rutgers University, 08854, New Brunswick, NJ, 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": "2018-04-25", 
    "datePublishedReg": "2018-04-25", 
    "description": "The online labeling problem (also known as the file maintenance problem), is a natural algorithmic problem that has arisen as a buidling block for data structures. A stream of distinct integer items is to be assigned labels online from a label set \\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}$$\\{1,\\ldots ,m\\}$$\\end{document} so that the order of the labels respects the natural order of the items. Maintaining order on the labels may require relabeling items. The algorithm pays 1 each time an item is labeled or relabeled and the goal of the algorithm is to minimize the total cost.We survey upper and lower bounds and open problems in both the deterministic and randomized setting.", 
    "editor": [
      {
        "familyName": "Fomin", 
        "givenName": "Fedor V.", 
        "type": "Person"
      }, 
      {
        "familyName": "Podolskii", 
        "givenName": "Vladimir V.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-90530-3_3", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-319-90529-7", 
        "978-3-319-90530-3"
      ], 
      "name": "Computer Science \u2013 Theory and Applications", 
      "type": "Book"
    }, 
    "keywords": [
      "data structure", 
      "online labeling problem", 
      "label set", 
      "labeling problem", 
      "algorithmic problems", 
      "natural algorithmic problems", 
      "lower bounds", 
      "algorithm", 
      "open problem", 
      "labels", 
      "bounds", 
      "total cost", 
      "items", 
      "open question", 
      "order", 
      "set", 
      "streams", 
      "cost", 
      "goal", 
      "block", 
      "natural order", 
      "time", 
      "setting", 
      "questions", 
      "structure", 
      "problem"
    ], 
    "name": "Online Labeling: Algorithms, Lower Bounds and Open Questions", 
    "pagination": "23-28", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1103771365"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-90530-3_3"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-90530-3_3", 
      "https://app.dimensions.ai/details/publication/pub.1103771365"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-10-01T07:00", 
    "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_56.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-319-90530-3_3"
  }
]
 

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-319-90530-3_3'

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-319-90530-3_3'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-90530-3_3'

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-319-90530-3_3'


 

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

90 TRIPLES      22 PREDICATES      50 URIs      43 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-90530-3_3 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author Nbfa59813045d45e7a45ee35284a8dc77
4 schema:datePublished 2018-04-25
5 schema:datePublishedReg 2018-04-25
6 schema:description The online labeling problem (also known as the file maintenance problem), is a natural algorithmic problem that has arisen as a buidling block for data structures. A stream of distinct integer items is to be assigned labels online from a label set \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\{1,\ldots ,m\}$$\end{document} so that the order of the labels respects the natural order of the items. Maintaining order on the labels may require relabeling items. The algorithm pays 1 each time an item is labeled or relabeled and the goal of the algorithm is to minimize the total cost.We survey upper and lower bounds and open problems in both the deterministic and randomized setting.
7 schema:editor N0d4f142865fb418a853f725f7b939cef
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf Nf30768d91a154165b95189fa7b3f0c24
11 schema:keywords algorithm
12 algorithmic problems
13 block
14 bounds
15 cost
16 data structure
17 goal
18 items
19 label set
20 labeling problem
21 labels
22 lower bounds
23 natural algorithmic problems
24 natural order
25 online labeling problem
26 open problem
27 open question
28 order
29 problem
30 questions
31 set
32 setting
33 streams
34 structure
35 time
36 total cost
37 schema:name Online Labeling: Algorithms, Lower Bounds and Open Questions
38 schema:pagination 23-28
39 schema:productId N450162272a2d487c89aacb8083f69703
40 N910ca1ee41534a4eb79e3aba32d5bded
41 schema:publisher N9ac325a02c8040a79d876932591aeabf
42 schema:sameAs https://app.dimensions.ai/details/publication/pub.1103771365
43 https://doi.org/10.1007/978-3-319-90530-3_3
44 schema:sdDatePublished 2022-10-01T07:00
45 schema:sdLicense https://scigraph.springernature.com/explorer/license/
46 schema:sdPublisher Ncbaaec9db83245069023f7e4f6ddafec
47 schema:url https://doi.org/10.1007/978-3-319-90530-3_3
48 sgo:license sg:explorer/license/
49 sgo:sdDataset chapters
50 rdf:type schema:Chapter
51 N0d4f142865fb418a853f725f7b939cef rdf:first N1df7dc8da59b48c4b90c73a77d37a066
52 rdf:rest N7fc99b2b820c4f9aaea5a70286395ccc
53 N1df7dc8da59b48c4b90c73a77d37a066 schema:familyName Fomin
54 schema:givenName Fedor V.
55 rdf:type schema:Person
56 N450162272a2d487c89aacb8083f69703 schema:name dimensions_id
57 schema:value pub.1103771365
58 rdf:type schema:PropertyValue
59 N7fc99b2b820c4f9aaea5a70286395ccc rdf:first Nb803a166dc4a42df9a633a79978aaf6e
60 rdf:rest rdf:nil
61 N910ca1ee41534a4eb79e3aba32d5bded schema:name doi
62 schema:value 10.1007/978-3-319-90530-3_3
63 rdf:type schema:PropertyValue
64 N9ac325a02c8040a79d876932591aeabf schema:name Springer Nature
65 rdf:type schema:Organisation
66 Nb803a166dc4a42df9a633a79978aaf6e schema:familyName Podolskii
67 schema:givenName Vladimir V.
68 rdf:type schema:Person
69 Nbfa59813045d45e7a45ee35284a8dc77 rdf:first sg:person.011520224512.05
70 rdf:rest rdf:nil
71 Ncbaaec9db83245069023f7e4f6ddafec schema:name Springer Nature - SN SciGraph project
72 rdf:type schema:Organization
73 Nf30768d91a154165b95189fa7b3f0c24 schema:isbn 978-3-319-90529-7
74 978-3-319-90530-3
75 schema:name Computer Science – Theory and Applications
76 rdf:type schema:Book
77 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
78 schema:name Information and Computing Sciences
79 rdf:type schema:DefinedTerm
80 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
81 schema:name Artificial Intelligence and Image Processing
82 rdf:type schema:DefinedTerm
83 sg:person.011520224512.05 schema:affiliation grid-institutes:grid.430387.b
84 schema:familyName Saks
85 schema:givenName Michael
86 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05
87 rdf:type schema:Person
88 grid-institutes:grid.430387.b schema:alternateName Department of Mathematics, Rutgers University, 08854, New Brunswick, NJ, USA
89 schema:name Department of Mathematics, Rutgers University, 08854, New Brunswick, NJ, USA
90 rdf:type schema:Organization
 




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


...