Speed is more powerful than clairvoyance View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1998

AUTHORS

Piotr Berman , Chris Coulston

ABSTRACT

We consider the problem of preemptive non-clairvoyant scheduling on a single machine. In this model a scheduler receives a number of jobs at different times without prior knowledge of the future jobs or the required processing time of jobs that are not yet completed. We want to minimize the total response time, i.e. the sum of times each job takes from its release to completion. One particular algorithm, Balance, always schedules the job that was least processed so far. A comparison of an on-line scheduler running Balance against the optimal off-line shows a very large competitive ratio if both algorithms use machines of the same speed. However, it has been shown if Balance is run on a v times faster machine then the competitive ratio drops to at most 1 + 1/(v−1). This result showed that speed can almost be as good as clairvoyance. We show for v ≥ 2 the competitive ratio of Balance is 2/v. In other words, sufficiently high speed is more powerful than clairvoyance. More... »

PAGES

255-263

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bfb0054373

DOI

http://dx.doi.org/10.1007/bfb0054373

DIMENSIONS

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


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 Computer Science and Engineering, The Pennsylvania State University, 16802, University Park, PA, USA", 
          "id": "http://www.grid.ac/institutes/grid.29857.31", 
          "name": [
            "Department of Computer Science and Engineering, The Pennsylvania State University, 16802, University Park, PA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Berman", 
        "givenName": "Piotr", 
        "id": "sg:person.01274506210.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Engineering, The Pennsylvania State University, 16802, University Park, PA, USA", 
          "id": "http://www.grid.ac/institutes/grid.29857.31", 
          "name": [
            "Department of Computer Science and Engineering, The Pennsylvania State University, 16802, University Park, PA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Coulston", 
        "givenName": "Chris", 
        "id": "sg:person.010257152675.20", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010257152675.20"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1998", 
    "datePublishedReg": "1998-01-01", 
    "description": "We consider the problem of preemptive non-clairvoyant scheduling on a single machine. In this model a scheduler receives a number of jobs at different times without prior knowledge of the future jobs or the required processing time of jobs that are not yet completed. We want to minimize the total response time, i.e. the sum of times each job takes from its release to completion. One particular algorithm, Balance, always schedules the job that was least processed so far. A comparison of an on-line scheduler running Balance against the optimal off-line shows a very large competitive ratio if both algorithms use machines of the same speed. However, it has been shown if Balance is run on a v times faster machine then the competitive ratio drops to at most 1 + 1/(v\u22121). This result showed that speed can almost be as good as clairvoyance. We show for v \u2265 2 the competitive ratio of Balance is 2/v. In other words, sufficiently high speed is more powerful than clairvoyance.", 
    "editor": [
      {
        "familyName": "Arnborg", 
        "givenName": "Stefan", 
        "type": "Person"
      }, 
      {
        "familyName": "Ivansson", 
        "givenName": "Lars", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/bfb0054373", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-64682-2", 
        "978-3-540-69106-8"
      ], 
      "name": "Algorithm Theory \u2014 SWAT'98", 
      "type": "Book"
    }, 
    "keywords": [
      "competitive ratio", 
      "larger competitive ratios", 
      "particular algorithm", 
      "number of jobs", 
      "non-clairvoyant scheduling", 
      "single machine", 
      "fast machine", 
      "line scheduler", 
      "algorithm", 
      "prior knowledge", 
      "same speed", 
      "total response time", 
      "scheduler", 
      "processing time", 
      "sum of time", 
      "speed", 
      "scheduling", 
      "high speed", 
      "sum", 
      "problem", 
      "machine", 
      "model", 
      "response time", 
      "clairvoyance", 
      "time", 
      "number", 
      "ratio", 
      "jobs", 
      "balance", 
      "results", 
      "comparison", 
      "different times", 
      "lines", 
      "knowledge", 
      "future jobs", 
      "completion", 
      "words", 
      "release"
    ], 
    "name": "Speed is more powerful than clairvoyance", 
    "pagination": "255-263", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1008132074"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bfb0054373"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/bfb0054373", 
      "https://app.dimensions.ai/details/publication/pub.1008132074"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-08-04T17:17", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220804/entities/gbq_results/chapter/chapter_270.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/bfb0054373"
  }
]
 

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

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

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bfb0054373'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bfb0054373'


 

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

109 TRIPLES      22 PREDICATES      63 URIs      56 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bfb0054373 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author N104415b53bb44563922c0e677ea49d5e
4 schema:datePublished 1998
5 schema:datePublishedReg 1998-01-01
6 schema:description We consider the problem of preemptive non-clairvoyant scheduling on a single machine. In this model a scheduler receives a number of jobs at different times without prior knowledge of the future jobs or the required processing time of jobs that are not yet completed. We want to minimize the total response time, i.e. the sum of times each job takes from its release to completion. One particular algorithm, Balance, always schedules the job that was least processed so far. A comparison of an on-line scheduler running Balance against the optimal off-line shows a very large competitive ratio if both algorithms use machines of the same speed. However, it has been shown if Balance is run on a v times faster machine then the competitive ratio drops to at most 1 + 1/(v−1). This result showed that speed can almost be as good as clairvoyance. We show for v ≥ 2 the competitive ratio of Balance is 2/v. In other words, sufficiently high speed is more powerful than clairvoyance.
7 schema:editor Naa0c40962f664ac3be54ca8099a790b7
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf Nd5b407ea5fbf4e449de813739d934338
11 schema:keywords algorithm
12 balance
13 clairvoyance
14 comparison
15 competitive ratio
16 completion
17 different times
18 fast machine
19 future jobs
20 high speed
21 jobs
22 knowledge
23 larger competitive ratios
24 line scheduler
25 lines
26 machine
27 model
28 non-clairvoyant scheduling
29 number
30 number of jobs
31 particular algorithm
32 prior knowledge
33 problem
34 processing time
35 ratio
36 release
37 response time
38 results
39 same speed
40 scheduler
41 scheduling
42 single machine
43 speed
44 sum
45 sum of time
46 time
47 total response time
48 words
49 schema:name Speed is more powerful than clairvoyance
50 schema:pagination 255-263
51 schema:productId N2dd6f99061ec4ff484bdc6d3dd2f7d1d
52 Nb7422423504e43cca54e6f3ad70deb38
53 schema:publisher Nc4a5a2b4d59040c79b96f4389a39e15b
54 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008132074
55 https://doi.org/10.1007/bfb0054373
56 schema:sdDatePublished 2022-08-04T17:17
57 schema:sdLicense https://scigraph.springernature.com/explorer/license/
58 schema:sdPublisher Nff2c38d2ef2d4decb613a5bc19ebed4b
59 schema:url https://doi.org/10.1007/bfb0054373
60 sgo:license sg:explorer/license/
61 sgo:sdDataset chapters
62 rdf:type schema:Chapter
63 N104415b53bb44563922c0e677ea49d5e rdf:first sg:person.01274506210.27
64 rdf:rest Nb79ba788398d4d348d3e3bf21cd2d96c
65 N212c598a98734a8386b037c88977cd7b schema:familyName Arnborg
66 schema:givenName Stefan
67 rdf:type schema:Person
68 N2dd6f99061ec4ff484bdc6d3dd2f7d1d schema:name dimensions_id
69 schema:value pub.1008132074
70 rdf:type schema:PropertyValue
71 N33fd1f5efbe84cf3bbc266989d34c1d5 schema:familyName Ivansson
72 schema:givenName Lars
73 rdf:type schema:Person
74 N5a52960e0b1f416eb5eb86aa3abf8b22 rdf:first N33fd1f5efbe84cf3bbc266989d34c1d5
75 rdf:rest rdf:nil
76 Naa0c40962f664ac3be54ca8099a790b7 rdf:first N212c598a98734a8386b037c88977cd7b
77 rdf:rest N5a52960e0b1f416eb5eb86aa3abf8b22
78 Nb7422423504e43cca54e6f3ad70deb38 schema:name doi
79 schema:value 10.1007/bfb0054373
80 rdf:type schema:PropertyValue
81 Nb79ba788398d4d348d3e3bf21cd2d96c rdf:first sg:person.010257152675.20
82 rdf:rest rdf:nil
83 Nc4a5a2b4d59040c79b96f4389a39e15b schema:name Springer Nature
84 rdf:type schema:Organisation
85 Nd5b407ea5fbf4e449de813739d934338 schema:isbn 978-3-540-64682-2
86 978-3-540-69106-8
87 schema:name Algorithm Theory — SWAT'98
88 rdf:type schema:Book
89 Nff2c38d2ef2d4decb613a5bc19ebed4b schema:name Springer Nature - SN SciGraph project
90 rdf:type schema:Organization
91 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
92 schema:name Information and Computing Sciences
93 rdf:type schema:DefinedTerm
94 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
95 schema:name Artificial Intelligence and Image Processing
96 rdf:type schema:DefinedTerm
97 sg:person.010257152675.20 schema:affiliation grid-institutes:grid.29857.31
98 schema:familyName Coulston
99 schema:givenName Chris
100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010257152675.20
101 rdf:type schema:Person
102 sg:person.01274506210.27 schema:affiliation grid-institutes:grid.29857.31
103 schema:familyName Berman
104 schema:givenName Piotr
105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27
106 rdf:type schema:Person
107 grid-institutes:grid.29857.31 schema:alternateName Department of Computer Science and Engineering, The Pennsylvania State University, 16802, University Park, PA, USA
108 schema:name Department of Computer Science and Engineering, The Pennsylvania State University, 16802, University Park, PA, USA
109 rdf:type schema:Organization
 




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


...