On-line load balancing for related machines View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1997

AUTHORS

Piotr Berman , Moses Charikar , Marek Karpinski

ABSTRACT

We consider the problem of scheduling permanent jobs on related machines in an on-line fashion. We design a new algorithm that achieves the competitive ratio of 3 + √8 ≈ 5.828 for the deterministic version, and 3.31/ln 2.155 ≈ 4.311 for its randomized variant, improving the previous competitive ratios of 8 and 2e ≈ 5.436. We also prove lower bounds of 2.4380 on the competitive ratio of deterministic algorithms and 1.8372 on the competitive ratio of randomized algorithms for this problem. More... »

PAGES

116-125

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-63307-3_52

DOI

http://dx.doi.org/10.1007/3-540-63307-3_52

DIMENSIONS

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


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": "The Pennsylvania State University, 16802, University Park, PA, USA", 
          "id": "http://www.grid.ac/institutes/grid.29857.31", 
          "name": [
            "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": "Stanford University, 94305-9045, Stanford, CA", 
          "id": "http://www.grid.ac/institutes/grid.168010.e", 
          "name": [
            "Stanford University, 94305-9045, Stanford, CA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Charikar", 
        "givenName": "Moses", 
        "id": "sg:person.01017615614.29", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01017615614.29"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "International Computer Science Institute, University of Bonn, 53117 Bonn, Berkeley", 
          "id": "http://www.grid.ac/institutes/grid.10388.32", 
          "name": [
            "International Computer Science Institute, University of Bonn, 53117 Bonn, Berkeley"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Karpinski", 
        "givenName": "Marek", 
        "id": "sg:person.011636042271.02", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1997", 
    "datePublishedReg": "1997-01-01", 
    "description": "We consider the problem of scheduling permanent jobs on related machines in an on-line fashion. We design a new algorithm that achieves the competitive ratio of 3 + \u221a8 \u2248 5.828 for the deterministic version, and 3.31/ln 2.155 \u2248 4.311 for its randomized variant, improving the previous competitive ratios of 8 and 2e \u2248 5.436. We also prove lower bounds of 2.4380 on the competitive ratio of deterministic algorithms and 1.8372 on the competitive ratio of randomized algorithms for this problem.", 
    "editor": [
      {
        "familyName": "Dehne", 
        "givenName": "Frank", 
        "type": "Person"
      }, 
      {
        "familyName": "Rau-Chaplin", 
        "givenName": "Andrew", 
        "type": "Person"
      }, 
      {
        "familyName": "Sack", 
        "givenName": "J\u00f6rg-R\u00fcdiger", 
        "type": "Person"
      }, 
      {
        "familyName": "Tamassia", 
        "givenName": "Roberto", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-63307-3_52", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-63307-5", 
        "978-3-540-69422-9"
      ], 
      "name": "Algorithms and Data Structures", 
      "type": "Book"
    }, 
    "keywords": [
      "competitive ratio", 
      "related machines", 
      "line fashion", 
      "randomized algorithm", 
      "deterministic algorithm", 
      "new algorithm", 
      "algorithm", 
      "machine", 
      "randomized variant", 
      "deterministic version", 
      "lower bounds", 
      "jobs", 
      "version", 
      "bounds", 
      "fashion", 
      "load", 
      "variants", 
      "line load", 
      "ratio", 
      "problem", 
      "permanent jobs"
    ], 
    "name": "On-line load balancing for related machines", 
    "pagination": "116-125", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1003220286"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-63307-3_52"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-63307-3_52", 
      "https://app.dimensions.ai/details/publication/pub.1003220286"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-08-04T17:22", 
    "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_87.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-63307-3_52"
  }
]
 

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-63307-3_52'

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-63307-3_52'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-63307-3_52'

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-63307-3_52'


 

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

115 TRIPLES      22 PREDICATES      46 URIs      39 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-63307-3_52 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author N17a0c0c8bd4f41f49e2ce675331e51ac
4 schema:datePublished 1997
5 schema:datePublishedReg 1997-01-01
6 schema:description We consider the problem of scheduling permanent jobs on related machines in an on-line fashion. We design a new algorithm that achieves the competitive ratio of 3 + √8 ≈ 5.828 for the deterministic version, and 3.31/ln 2.155 ≈ 4.311 for its randomized variant, improving the previous competitive ratios of 8 and 2e ≈ 5.436. We also prove lower bounds of 2.4380 on the competitive ratio of deterministic algorithms and 1.8372 on the competitive ratio of randomized algorithms for this problem.
7 schema:editor N355345358fe0439c9bb14c48dea76f20
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N9f6f9211c4ad49fca5b8cbda1142d79e
11 schema:keywords algorithm
12 bounds
13 competitive ratio
14 deterministic algorithm
15 deterministic version
16 fashion
17 jobs
18 line fashion
19 line load
20 load
21 lower bounds
22 machine
23 new algorithm
24 permanent jobs
25 problem
26 randomized algorithm
27 randomized variant
28 ratio
29 related machines
30 variants
31 version
32 schema:name On-line load balancing for related machines
33 schema:pagination 116-125
34 schema:productId N1bdf2ff988f142f1bad4ae0cb2bc07e2
35 N6ac53102db3446b2bd23f74813adf036
36 schema:publisher Ne721ab0c31bf42a8baacd8ae9612cad0
37 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003220286
38 https://doi.org/10.1007/3-540-63307-3_52
39 schema:sdDatePublished 2022-08-04T17:22
40 schema:sdLicense https://scigraph.springernature.com/explorer/license/
41 schema:sdPublisher Ne38165a1f52246518a824ca8f49da5d2
42 schema:url https://doi.org/10.1007/3-540-63307-3_52
43 sgo:license sg:explorer/license/
44 sgo:sdDataset chapters
45 rdf:type schema:Chapter
46 N0121b1f73d9d4a768bfe0b3ee89a1c1e schema:familyName Tamassia
47 schema:givenName Roberto
48 rdf:type schema:Person
49 N0f50c889e56147c19202be9d3cfe0dca schema:familyName Rau-Chaplin
50 schema:givenName Andrew
51 rdf:type schema:Person
52 N13769ad8a0934f6198cd0775248236d3 rdf:first N0f50c889e56147c19202be9d3cfe0dca
53 rdf:rest Ne3ea55c4b7874393b939105773a81d2e
54 N17a0c0c8bd4f41f49e2ce675331e51ac rdf:first sg:person.01274506210.27
55 rdf:rest N88dc908f71ba4d768b6f1d6102cc4285
56 N1bdf2ff988f142f1bad4ae0cb2bc07e2 schema:name dimensions_id
57 schema:value pub.1003220286
58 rdf:type schema:PropertyValue
59 N355345358fe0439c9bb14c48dea76f20 rdf:first N75ea09321f7d45bb833adacd06d23ddb
60 rdf:rest N13769ad8a0934f6198cd0775248236d3
61 N6ac53102db3446b2bd23f74813adf036 schema:name doi
62 schema:value 10.1007/3-540-63307-3_52
63 rdf:type schema:PropertyValue
64 N75ea09321f7d45bb833adacd06d23ddb schema:familyName Dehne
65 schema:givenName Frank
66 rdf:type schema:Person
67 N88dc908f71ba4d768b6f1d6102cc4285 rdf:first sg:person.01017615614.29
68 rdf:rest Nd354704392494444b3e59282f45256eb
69 N959261ccd00042548f307bf734b4f085 schema:familyName Sack
70 schema:givenName Jörg-Rüdiger
71 rdf:type schema:Person
72 N9f6f9211c4ad49fca5b8cbda1142d79e schema:isbn 978-3-540-63307-5
73 978-3-540-69422-9
74 schema:name Algorithms and Data Structures
75 rdf:type schema:Book
76 Nc0ee22de925e4fc38033e628f3d3d791 rdf:first N0121b1f73d9d4a768bfe0b3ee89a1c1e
77 rdf:rest rdf:nil
78 Nd354704392494444b3e59282f45256eb rdf:first sg:person.011636042271.02
79 rdf:rest rdf:nil
80 Ne38165a1f52246518a824ca8f49da5d2 schema:name Springer Nature - SN SciGraph project
81 rdf:type schema:Organization
82 Ne3ea55c4b7874393b939105773a81d2e rdf:first N959261ccd00042548f307bf734b4f085
83 rdf:rest Nc0ee22de925e4fc38033e628f3d3d791
84 Ne721ab0c31bf42a8baacd8ae9612cad0 schema:name Springer Nature
85 rdf:type schema:Organisation
86 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
87 schema:name Information and Computing Sciences
88 rdf:type schema:DefinedTerm
89 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
90 schema:name Artificial Intelligence and Image Processing
91 rdf:type schema:DefinedTerm
92 sg:person.01017615614.29 schema:affiliation grid-institutes:grid.168010.e
93 schema:familyName Charikar
94 schema:givenName Moses
95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01017615614.29
96 rdf:type schema:Person
97 sg:person.011636042271.02 schema:affiliation grid-institutes:grid.10388.32
98 schema:familyName Karpinski
99 schema:givenName Marek
100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02
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.10388.32 schema:alternateName International Computer Science Institute, University of Bonn, 53117 Bonn, Berkeley
108 schema:name International Computer Science Institute, University of Bonn, 53117 Bonn, Berkeley
109 rdf:type schema:Organization
110 grid-institutes:grid.168010.e schema:alternateName Stanford University, 94305-9045, Stanford, CA
111 schema:name Stanford University, 94305-9045, Stanford, CA
112 rdf:type schema:Organization
113 grid-institutes:grid.29857.31 schema:alternateName The Pennsylvania State University, 16802, University Park, PA, USA
114 schema:name The Pennsylvania State University, 16802, University Park, PA, USA
115 rdf:type schema:Organization
 




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


...