On List Update and Work Function Algorithms View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1999

AUTHORS

Eric J. Anderson , Kris Hildrum , Anna R. Karlin , April Rasala , Michael Saks

ABSTRACT

The list update problem, a well-studied problem in dynamic data structures, can be described abstractly as a metrical task system. In this paper, we prove that a generic metrical task system algorithm, called the work function algorithm, has constant competitive ratio for list update. In the process, we present a new formulation of the well-known “list factoring” technique in terms of a partial order on the elements of the list. This approach leads to a new simple proof that a large class of online algorithms, including Move-To-Front, is (2 - 1/k)-competitive. More... »

PAGES

289-300

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-48481-7_26

DOI

http://dx.doi.org/10.1007/3-540-48481-7_26

DIMENSIONS

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


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": "Dept. of Computer Science, Univ. of Wash., Wash.", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Dept. of Computer Science, Univ. of Wash., Wash."
          ], 
          "type": "Organization"
        }, 
        "familyName": "Anderson", 
        "givenName": "Eric J.", 
        "id": "sg:person.012037165161.51", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012037165161.51"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Computer Science Div., Univ. of Calif., Calif.", 
          "id": "http://www.grid.ac/institutes/grid.30389.31", 
          "name": [
            "Computer Science Div., Univ. of Calif., Calif."
          ], 
          "type": "Organization"
        }, 
        "familyName": "Hildrum", 
        "givenName": "Kris", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Dept. of Computer Science, Univ. of Wash., Wash.", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Dept. of Computer Science, Univ. of Wash., Wash."
          ], 
          "type": "Organization"
        }, 
        "familyName": "Karlin", 
        "givenName": "Anna R.", 
        "id": "sg:person.013176064675.47", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013176064675.47"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Dept. of Computer Science, Dartmouth College, Dartmouth", 
          "id": "http://www.grid.ac/institutes/grid.254880.3", 
          "name": [
            "Dept. of Computer Science, Dartmouth College, Dartmouth"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Rasala", 
        "givenName": "April", 
        "id": "sg:person.016641712771.70", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016641712771.70"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Dept. of Mathematics, Rutgers Univ., Rutgers", 
          "id": "http://www.grid.ac/institutes/grid.430387.b", 
          "name": [
            "Dept. of Mathematics, Rutgers Univ., Rutgers"
          ], 
          "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": "1999", 
    "datePublishedReg": "1999-01-01", 
    "description": "The list update problem, a well-studied problem in dynamic data structures, can be described abstractly as a metrical task system. In this paper, we prove that a generic metrical task system algorithm, called the work function algorithm, has constant competitive ratio for list update. In the process, we present a new formulation of the well-known \u201clist factoring\u201d technique in terms of a partial order on the elements of the list. This approach leads to a new simple proof that a large class of online algorithms, including Move-To-Front, is (2 - 1/k)-competitive.", 
    "editor": [
      {
        "familyName": "Ne\u0161et\u0159il", 
        "givenName": "Jaroslav", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-48481-7_26", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-66251-8", 
        "978-3-540-48481-3"
      ], 
      "name": "Algorithms - ESA\u2019 99", 
      "type": "Book"
    }, 
    "keywords": [
      "work function algorithm", 
      "dynamic data structures", 
      "function algorithm", 
      "constant competitive ratio", 
      "metrical task systems", 
      "list update", 
      "data structure", 
      "update problem", 
      "online algorithm", 
      "list update problem", 
      "task systems", 
      "system algorithm", 
      "algorithm", 
      "competitive ratio", 
      "partial order", 
      "update", 
      "large class", 
      "factoring", 
      "proof", 
      "system", 
      "technique", 
      "simple proof", 
      "list", 
      "order", 
      "new formulation", 
      "class", 
      "terms", 
      "process", 
      "new simple proof", 
      "elements", 
      "formulation", 
      "structure", 
      "front", 
      "ratio", 
      "problem", 
      "paper", 
      "approach"
    ], 
    "name": "On List Update and Work Function Algorithms", 
    "pagination": "289-300", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1026845253"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-48481-7_26"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-48481-7_26", 
      "https://app.dimensions.ai/details/publication/pub.1026845253"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-10-01T06:54", 
    "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_18.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-48481-7_26"
  }
]
 

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/3-540-48481-7_26'

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/3-540-48481-7_26'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-48481-7_26'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-48481-7_26'


 

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

132 TRIPLES      22 PREDICATES      62 URIs      55 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-48481-7_26 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author N9217c25b350743bab367528b32091376
4 schema:datePublished 1999
5 schema:datePublishedReg 1999-01-01
6 schema:description The list update problem, a well-studied problem in dynamic data structures, can be described abstractly as a metrical task system. In this paper, we prove that a generic metrical task system algorithm, called the work function algorithm, has constant competitive ratio for list update. In the process, we present a new formulation of the well-known “list factoring” technique in terms of a partial order on the elements of the list. This approach leads to a new simple proof that a large class of online algorithms, including Move-To-Front, is (2 - 1/k)-competitive.
7 schema:editor N767d198f9c6d44bcb1f0b15f0d594caf
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N7d8b7da6f4b242f9a34cd672b3efc7b5
11 schema:keywords algorithm
12 approach
13 class
14 competitive ratio
15 constant competitive ratio
16 data structure
17 dynamic data structures
18 elements
19 factoring
20 formulation
21 front
22 function algorithm
23 large class
24 list
25 list update
26 list update problem
27 metrical task systems
28 new formulation
29 new simple proof
30 online algorithm
31 order
32 paper
33 partial order
34 problem
35 process
36 proof
37 ratio
38 simple proof
39 structure
40 system
41 system algorithm
42 task systems
43 technique
44 terms
45 update
46 update problem
47 work function algorithm
48 schema:name On List Update and Work Function Algorithms
49 schema:pagination 289-300
50 schema:productId N4658fe4813c44a4789c34d15ed704342
51 Nc6adbf04738b42f389202cf1d059b0d6
52 schema:publisher N727c2cefe7bc4f6ca53e3e659371e2e0
53 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026845253
54 https://doi.org/10.1007/3-540-48481-7_26
55 schema:sdDatePublished 2022-10-01T06:54
56 schema:sdLicense https://scigraph.springernature.com/explorer/license/
57 schema:sdPublisher Ncdcf94e85305437a96640aa72796e1d1
58 schema:url https://doi.org/10.1007/3-540-48481-7_26
59 sgo:license sg:explorer/license/
60 sgo:sdDataset chapters
61 rdf:type schema:Chapter
62 N2bd9b8303e524568806da1b538cd54b0 rdf:first Nf04baf25868c45f2ab17df6b03b48413
63 rdf:rest Ncb0ff9f4f228413eb1ea50c736bb02f8
64 N4658fe4813c44a4789c34d15ed704342 schema:name doi
65 schema:value 10.1007/3-540-48481-7_26
66 rdf:type schema:PropertyValue
67 N717ed5c81cee4cefb87c7dc141bb6365 schema:familyName Nešetřil
68 schema:givenName Jaroslav
69 rdf:type schema:Person
70 N727c2cefe7bc4f6ca53e3e659371e2e0 schema:name Springer Nature
71 rdf:type schema:Organisation
72 N72c239b8be9141eba14fecf63305a650 rdf:first sg:person.016641712771.70
73 rdf:rest Nc206c733fd5249b0a8126dd364371484
74 N767d198f9c6d44bcb1f0b15f0d594caf rdf:first N717ed5c81cee4cefb87c7dc141bb6365
75 rdf:rest rdf:nil
76 N7d8b7da6f4b242f9a34cd672b3efc7b5 schema:isbn 978-3-540-48481-3
77 978-3-540-66251-8
78 schema:name Algorithms - ESA’ 99
79 rdf:type schema:Book
80 N9217c25b350743bab367528b32091376 rdf:first sg:person.012037165161.51
81 rdf:rest N2bd9b8303e524568806da1b538cd54b0
82 Nc206c733fd5249b0a8126dd364371484 rdf:first sg:person.011520224512.05
83 rdf:rest rdf:nil
84 Nc6adbf04738b42f389202cf1d059b0d6 schema:name dimensions_id
85 schema:value pub.1026845253
86 rdf:type schema:PropertyValue
87 Ncb0ff9f4f228413eb1ea50c736bb02f8 rdf:first sg:person.013176064675.47
88 rdf:rest N72c239b8be9141eba14fecf63305a650
89 Ncdcf94e85305437a96640aa72796e1d1 schema:name Springer Nature - SN SciGraph project
90 rdf:type schema:Organization
91 Nf04baf25868c45f2ab17df6b03b48413 schema:affiliation grid-institutes:grid.30389.31
92 schema:familyName Hildrum
93 schema:givenName Kris
94 rdf:type schema:Person
95 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
96 schema:name Information and Computing Sciences
97 rdf:type schema:DefinedTerm
98 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
99 schema:name Artificial Intelligence and Image Processing
100 rdf:type schema:DefinedTerm
101 sg:person.011520224512.05 schema:affiliation grid-institutes:grid.430387.b
102 schema:familyName Saks
103 schema:givenName Michael
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05
105 rdf:type schema:Person
106 sg:person.012037165161.51 schema:affiliation grid-institutes:None
107 schema:familyName Anderson
108 schema:givenName Eric J.
109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012037165161.51
110 rdf:type schema:Person
111 sg:person.013176064675.47 schema:affiliation grid-institutes:None
112 schema:familyName Karlin
113 schema:givenName Anna R.
114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013176064675.47
115 rdf:type schema:Person
116 sg:person.016641712771.70 schema:affiliation grid-institutes:grid.254880.3
117 schema:familyName Rasala
118 schema:givenName April
119 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016641712771.70
120 rdf:type schema:Person
121 grid-institutes:None schema:alternateName Dept. of Computer Science, Univ. of Wash., Wash.
122 schema:name Dept. of Computer Science, Univ. of Wash., Wash.
123 rdf:type schema:Organization
124 grid-institutes:grid.254880.3 schema:alternateName Dept. of Computer Science, Dartmouth College, Dartmouth
125 schema:name Dept. of Computer Science, Dartmouth College, Dartmouth
126 rdf:type schema:Organization
127 grid-institutes:grid.30389.31 schema:alternateName Computer Science Div., Univ. of Calif., Calif.
128 schema:name Computer Science Div., Univ. of Calif., Calif.
129 rdf:type schema:Organization
130 grid-institutes:grid.430387.b schema:alternateName Dept. of Mathematics, Rutgers Univ., Rutgers
131 schema:name Dept. of Mathematics, Rutgers Univ., Rutgers
132 rdf:type schema:Organization
 




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


...