Competitive analysis of the on-line algorithms for multiple stacks systems View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1992

AUTHORS

Been-Chian Chien , Rong-Jaye Chen , Wei-Pang Yang

ABSTRACT

An on-line problem is one in which an algorithm must handle a sequence of requests, satisfying each request without knowledge of the future requests. A competitive algorithm is an on-line algorithm whose cost is bounded by the cost of any other algorithm, even the algorithm is an optimal off-line algorithm, multipling a constant. This paper discusses the algorithms used to manipulate the multiple stacks problem, which is one of the on-line problems. We find the optimal off-line algorithm first, then show that the Knuth's algorithm is not a competitive algorithm, but Garwick's algorithm is competitive when the number of stacks n is 2. Furthermore, the competitive ratio found here is a low bound if the Garwick's algorithm is also a competitive algorithm for n≥3. More... »

PAGES

78-87

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-56279-6_60

DOI

http://dx.doi.org/10.1007/3-540-56279-6_60

DIMENSIONS

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


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 and Information Engineering, National Chiao Tung University, R.O.C.", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Institute of Computer Science and Information Engineering, National Chiao Tung University, R.O.C."
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chien", 
        "givenName": "Been-Chian", 
        "id": "sg:person.014505766526.30", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014505766526.30"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Institute of Computer Science and Information Engineering, National Chiao Tung University, R.O.C.", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Institute of Computer Science and Information Engineering, National Chiao Tung University, R.O.C."
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chen", 
        "givenName": "Rong-Jaye", 
        "id": "sg:person.010062037474.96", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010062037474.96"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer and Information Science, National Chiao Tung University, Hsinchu, Taiwan, 30050, R.O.C.", 
          "id": "http://www.grid.ac/institutes/grid.260539.b", 
          "name": [
            "Department of Computer and Information Science, National Chiao Tung University, Hsinchu, Taiwan, 30050, R.O.C."
          ], 
          "type": "Organization"
        }, 
        "familyName": "Yang", 
        "givenName": "Wei-Pang", 
        "id": "sg:person.014374171260.51", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014374171260.51"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1992", 
    "datePublishedReg": "1992-01-01", 
    "description": "An on-line problem is one in which an algorithm must handle a sequence of requests, satisfying each request without knowledge of the future requests. A competitive algorithm is an on-line algorithm whose cost is bounded by the cost of any other algorithm, even the algorithm is an optimal off-line algorithm, multipling a constant. This paper discusses the algorithms used to manipulate the multiple stacks problem, which is one of the on-line problems. We find the optimal off-line algorithm first, then show that the Knuth's algorithm is not a competitive algorithm, but Garwick's algorithm is competitive when the number of stacks n is 2. Furthermore, the competitive ratio found here is a low bound if the Garwick's algorithm is also a competitive algorithm for n\u22653.", 
    "editor": [
      {
        "familyName": "Ibaraki", 
        "givenName": "Toshihide", 
        "type": "Person"
      }, 
      {
        "familyName": "Inagaki", 
        "givenName": "Yasuyoshi", 
        "type": "Person"
      }, 
      {
        "familyName": "Iwama", 
        "givenName": "Kazuo", 
        "type": "Person"
      }, 
      {
        "familyName": "Nishizeki", 
        "givenName": "Takao", 
        "type": "Person"
      }, 
      {
        "familyName": "Yamashita", 
        "givenName": "Masafumi", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-56279-6_60", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-56279-5", 
        "978-3-540-47501-9"
      ], 
      "name": "Algorithms and Computation", 
      "type": "Book"
    }, 
    "keywords": [
      "line algorithm", 
      "competitive algorithm", 
      "line problem", 
      "stacks problem", 
      "sequence of requests", 
      "future requests", 
      "Knuth's algorithm", 
      "competitive ratio", 
      "algorithm", 
      "competitive analysis", 
      "requests", 
      "problem", 
      "stack system", 
      "cost", 
      "constants", 
      "system", 
      "number", 
      "knowledge", 
      "analysis", 
      "sequence", 
      "ratio", 
      "paper"
    ], 
    "name": "Competitive analysis of the on-line algorithms for multiple stacks systems", 
    "pagination": "78-87", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1045840653"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-56279-6_60"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-56279-6_60", 
      "https://app.dimensions.ai/details/publication/pub.1045840653"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:47", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_375.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-56279-6_60"
  }
]
 

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-56279-6_60'

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-56279-6_60'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-56279-6_60'

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-56279-6_60'


 

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

119 TRIPLES      23 PREDICATES      48 URIs      41 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-56279-6_60 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author Nc693eab64c544e8bbd5a25bd95683a55
4 schema:datePublished 1992
5 schema:datePublishedReg 1992-01-01
6 schema:description An on-line problem is one in which an algorithm must handle a sequence of requests, satisfying each request without knowledge of the future requests. A competitive algorithm is an on-line algorithm whose cost is bounded by the cost of any other algorithm, even the algorithm is an optimal off-line algorithm, multipling a constant. This paper discusses the algorithms used to manipulate the multiple stacks problem, which is one of the on-line problems. We find the optimal off-line algorithm first, then show that the Knuth's algorithm is not a competitive algorithm, but Garwick's algorithm is competitive when the number of stacks n is 2. Furthermore, the competitive ratio found here is a low bound if the Garwick's algorithm is also a competitive algorithm for n≥3.
7 schema:editor N35169c32f6dc4f1bbc0efa36cad3bbe2
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N9e4f042c47ee4db0920766a8d5963f7e
12 schema:keywords Knuth's algorithm
13 algorithm
14 analysis
15 competitive algorithm
16 competitive analysis
17 competitive ratio
18 constants
19 cost
20 future requests
21 knowledge
22 line algorithm
23 line problem
24 number
25 paper
26 problem
27 ratio
28 requests
29 sequence
30 sequence of requests
31 stack system
32 stacks problem
33 system
34 schema:name Competitive analysis of the on-line algorithms for multiple stacks systems
35 schema:pagination 78-87
36 schema:productId N4e880202b6ad41d0a20771e9d1c1afc6
37 N94d8a6dc7d6049648b40993956f62173
38 schema:publisher N1270bbe2828c46ee8b4deec8bf135979
39 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045840653
40 https://doi.org/10.1007/3-540-56279-6_60
41 schema:sdDatePublished 2022-05-20T07:47
42 schema:sdLicense https://scigraph.springernature.com/explorer/license/
43 schema:sdPublisher N954160e7125d4d2490c002c2a7343a8f
44 schema:url https://doi.org/10.1007/3-540-56279-6_60
45 sgo:license sg:explorer/license/
46 sgo:sdDataset chapters
47 rdf:type schema:Chapter
48 N1270bbe2828c46ee8b4deec8bf135979 schema:name Springer Nature
49 rdf:type schema:Organisation
50 N210f22ceb08047cd88363e005a845668 schema:familyName Nishizeki
51 schema:givenName Takao
52 rdf:type schema:Person
53 N35169c32f6dc4f1bbc0efa36cad3bbe2 rdf:first Na877880b20b949889f8c4727116130a1
54 rdf:rest N6eaddea86ec642f0ac1841eaefe1af0b
55 N4e880202b6ad41d0a20771e9d1c1afc6 schema:name doi
56 schema:value 10.1007/3-540-56279-6_60
57 rdf:type schema:PropertyValue
58 N64bba88217e84edda2ca53ec0578ed69 schema:familyName Iwama
59 schema:givenName Kazuo
60 rdf:type schema:Person
61 N6e0158aa1dd24dc9b86d155204a46159 rdf:first sg:person.010062037474.96
62 rdf:rest Nac677722b4cb4468a45424d647089600
63 N6eaddea86ec642f0ac1841eaefe1af0b rdf:first N9e23c6f2159d47c4a24c6475edd58870
64 rdf:rest Nf2e75075ddd14088af98d65efd5e94e1
65 N87797bdd21234dd28f876274a41ebac4 schema:familyName Yamashita
66 schema:givenName Masafumi
67 rdf:type schema:Person
68 N94d8a6dc7d6049648b40993956f62173 schema:name dimensions_id
69 schema:value pub.1045840653
70 rdf:type schema:PropertyValue
71 N954160e7125d4d2490c002c2a7343a8f schema:name Springer Nature - SN SciGraph project
72 rdf:type schema:Organization
73 N9e23c6f2159d47c4a24c6475edd58870 schema:familyName Inagaki
74 schema:givenName Yasuyoshi
75 rdf:type schema:Person
76 N9e4f042c47ee4db0920766a8d5963f7e schema:isbn 978-3-540-47501-9
77 978-3-540-56279-5
78 schema:name Algorithms and Computation
79 rdf:type schema:Book
80 Na877880b20b949889f8c4727116130a1 schema:familyName Ibaraki
81 schema:givenName Toshihide
82 rdf:type schema:Person
83 Nac677722b4cb4468a45424d647089600 rdf:first sg:person.014374171260.51
84 rdf:rest rdf:nil
85 Nc693eab64c544e8bbd5a25bd95683a55 rdf:first sg:person.014505766526.30
86 rdf:rest N6e0158aa1dd24dc9b86d155204a46159
87 Nd6c050317a1e46e088170beb7eb728b8 rdf:first N87797bdd21234dd28f876274a41ebac4
88 rdf:rest rdf:nil
89 Ne868db79e6bd481fb905b02f8fbfd1d4 rdf:first N210f22ceb08047cd88363e005a845668
90 rdf:rest Nd6c050317a1e46e088170beb7eb728b8
91 Nf2e75075ddd14088af98d65efd5e94e1 rdf:first N64bba88217e84edda2ca53ec0578ed69
92 rdf:rest Ne868db79e6bd481fb905b02f8fbfd1d4
93 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
94 schema:name Information and Computing Sciences
95 rdf:type schema:DefinedTerm
96 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
97 schema:name Artificial Intelligence and Image Processing
98 rdf:type schema:DefinedTerm
99 sg:person.010062037474.96 schema:affiliation grid-institutes:None
100 schema:familyName Chen
101 schema:givenName Rong-Jaye
102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010062037474.96
103 rdf:type schema:Person
104 sg:person.014374171260.51 schema:affiliation grid-institutes:grid.260539.b
105 schema:familyName Yang
106 schema:givenName Wei-Pang
107 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014374171260.51
108 rdf:type schema:Person
109 sg:person.014505766526.30 schema:affiliation grid-institutes:None
110 schema:familyName Chien
111 schema:givenName Been-Chian
112 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014505766526.30
113 rdf:type schema:Person
114 grid-institutes:None schema:alternateName Institute of Computer Science and Information Engineering, National Chiao Tung University, R.O.C.
115 schema:name Institute of Computer Science and Information Engineering, National Chiao Tung University, R.O.C.
116 rdf:type schema:Organization
117 grid-institutes:grid.260539.b schema:alternateName Department of Computer and Information Science, National Chiao Tung University, Hsinchu, Taiwan, 30050, R.O.C.
118 schema:name Department of Computer and Information Science, National Chiao Tung University, Hsinchu, Taiwan, 30050, R.O.C.
119 rdf:type schema:Organization
 




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


...