Online Load Balancing Made Simple: Greedy Strikes Back View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2003

AUTHORS

Pilu Crescenzi , Giorgio Gambosi , Gaia Nicosia , Paolo Penna , Walter Unger

ABSTRACT

We provide a new simpler approach to the on-line load balancing problem in the case of restricted assignment of temporary weighted tasks. The approach is very general and allows to derive online distributed algorithms whose competitive ratio is characterized by some combinatorial properties of the underlying graph representing the problem. Some of our results are obtained via a combinatorial characterization of those graphs for which our technique yields O(\( \sqrt n \))-competitive algorithms. More... »

PAGES

1108-1122

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-45061-0_85

DOI

http://dx.doi.org/10.1007/3-540-45061-0_85

DIMENSIONS

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


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Florence", 
          "id": "https://www.grid.ac/institutes/grid.8404.8", 
          "name": [
            "Dipartimento di Sistemi ed Informatica, Universit\u00e0 di Firenze, via C. Lombroso 6/17, I-50134\u00a0Firenze, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Crescenzi", 
        "givenName": "Pilu", 
        "id": "sg:person.07475505355.50", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07475505355.50"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Rome Tor Vergata", 
          "id": "https://www.grid.ac/institutes/grid.6530.0", 
          "name": [
            "Dipartimento di Matematica, Universit\u00e0 di Roma \u201cTor Vergata\u201d, via della Ricerca Scientifica, I-00133\u00a0Roma, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Gambosi", 
        "givenName": "Giorgio", 
        "id": "sg:person.011355176201.51", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011355176201.51"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Roma Tre University", 
          "id": "https://www.grid.ac/institutes/grid.8509.4", 
          "name": [
            "Dipartimento di Informatica e Automazione, Universit\u00e0 degli studi \u201cRoma Tre\u201d, via della Vasca Navale 79, I-00146\u00a0Roma, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Nicosia", 
        "givenName": "Gaia", 
        "id": "sg:person.010145160357.51", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010145160357.51"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Salerno", 
          "id": "https://www.grid.ac/institutes/grid.11780.3f", 
          "name": [
            "Dipartimento di Informatica ed Applicazioni \u201cR.M. Capocelli\u201d, Universit\u00e0 di Salerno, via S. Allende 2, I-84081\u00a0Baronissi (SA), Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Penna", 
        "givenName": "Paolo", 
        "id": "sg:person.013624103516.76", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013624103516.76"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "RWTH Aachen University", 
          "id": "https://www.grid.ac/institutes/grid.1957.a", 
          "name": [
            "RWTH Aachen, Ahornstrasse 55, 52056\u00a0Aachen, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Unger", 
        "givenName": "Walter", 
        "id": "sg:person.016230612433.51", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016230612433.51"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/s0020-0190(97)00085-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1003156187"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01585745", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006292857", 
          "https://doi.org/10.1007/bf01585745"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/pl00009214", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007091005", 
          "https://doi.org/10.1007/pl00009214"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0304-3975(94)90153-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012616905"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1006/jagm.1995.0799", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1015422383"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01918335", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028360600", 
          "https://doi.org/10.1007/bf01918335"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0041-1647(70)90196-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032750498"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0041-1647(70)90196-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032750498"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1006/jagm.1995.1008", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1034855085"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s0097539798346135", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062880285"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2003", 
    "datePublishedReg": "2003-01-01", 
    "description": "We provide a new simpler approach to the on-line load balancing problem in the case of restricted assignment of temporary weighted tasks. The approach is very general and allows to derive online distributed algorithms whose competitive ratio is characterized by some combinatorial properties of the underlying graph representing the problem. Some of our results are obtained via a combinatorial characterization of those graphs for which our technique yields O(\\( \\sqrt n \\))-competitive algorithms.", 
    "editor": [
      {
        "familyName": "Baeten", 
        "givenName": "Jos C. M.", 
        "type": "Person"
      }, 
      {
        "familyName": "Lenstra", 
        "givenName": "Jan Karel", 
        "type": "Person"
      }, 
      {
        "familyName": "Parrow", 
        "givenName": "Joachim", 
        "type": "Person"
      }, 
      {
        "familyName": "Woeginger", 
        "givenName": "Gerhard J.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-45061-0_85", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isFundedItemOf": [
      {
        "id": "sg:grant.3750114", 
        "type": "MonetaryGrant"
      }
    ], 
    "isPartOf": {
      "isbn": [
        "978-3-540-40493-4", 
        "978-3-540-45061-0"
      ], 
      "name": "Automata, Languages and Programming", 
      "type": "Book"
    }, 
    "name": "Online Load Balancing Made Simple: Greedy Strikes Back", 
    "pagination": "1108-1122", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-45061-0_85"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "94133630bed447fd5d4c5e2a6c435389d8768a64d075bc8bccc639d8a14b3bda"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1031082725"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-45061-0_85", 
      "https://app.dimensions.ai/details/publication/pub.1031082725"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T23:52", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8697_00000262.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/3-540-45061-0_85"
  }
]
 

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-45061-0_85'

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-45061-0_85'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-45061-0_85'

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-45061-0_85'


 

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

152 TRIPLES      23 PREDICATES      36 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-45061-0_85 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N5f9a4c6791d4453e9484e859e5a29feb
4 schema:citation sg:pub.10.1007/bf01585745
5 sg:pub.10.1007/bf01918335
6 sg:pub.10.1007/pl00009214
7 https://doi.org/10.1006/jagm.1995.0799
8 https://doi.org/10.1006/jagm.1995.1008
9 https://doi.org/10.1016/0041-1647(70)90196-6
10 https://doi.org/10.1016/0304-3975(94)90153-8
11 https://doi.org/10.1016/s0020-0190(97)00085-9
12 https://doi.org/10.1137/s0097539798346135
13 schema:datePublished 2003
14 schema:datePublishedReg 2003-01-01
15 schema:description We provide a new simpler approach to the on-line load balancing problem in the case of restricted assignment of temporary weighted tasks. The approach is very general and allows to derive online distributed algorithms whose competitive ratio is characterized by some combinatorial properties of the underlying graph representing the problem. Some of our results are obtained via a combinatorial characterization of those graphs for which our technique yields O(\( \sqrt n \))-competitive algorithms.
16 schema:editor N6bfb674d67ea4975b17cfa011b622f1d
17 schema:genre chapter
18 schema:inLanguage en
19 schema:isAccessibleForFree false
20 schema:isPartOf N401448903b1e4090bf87d8eba8ec10a0
21 schema:name Online Load Balancing Made Simple: Greedy Strikes Back
22 schema:pagination 1108-1122
23 schema:productId N1f389fb106344cfeb416052f29d4638f
24 Ndf732132db19479293db67e588f74ff6
25 Ne834d914c99a4f50b4d896e6aa9257ee
26 schema:publisher Nf39e1cc8465648f380ed57aa942828de
27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031082725
28 https://doi.org/10.1007/3-540-45061-0_85
29 schema:sdDatePublished 2019-04-15T23:52
30 schema:sdLicense https://scigraph.springernature.com/explorer/license/
31 schema:sdPublisher N35b7e273da514897b9ae47ae7c972900
32 schema:url http://link.springer.com/10.1007/3-540-45061-0_85
33 sgo:license sg:explorer/license/
34 sgo:sdDataset chapters
35 rdf:type schema:Chapter
36 N04a3b4932eb84d409b5b29aa8801320e rdf:first sg:person.016230612433.51
37 rdf:rest rdf:nil
38 N1f389fb106344cfeb416052f29d4638f schema:name doi
39 schema:value 10.1007/3-540-45061-0_85
40 rdf:type schema:PropertyValue
41 N235e665a809841b78613108af0adaacd schema:familyName Woeginger
42 schema:givenName Gerhard J.
43 rdf:type schema:Person
44 N29bc57e730424ba2a44cf8226478429b schema:familyName Baeten
45 schema:givenName Jos C. M.
46 rdf:type schema:Person
47 N33127af5a7a840d08c16c5c777fc0f89 rdf:first N79073b3b3d9a470f9004c8ed9b10ff17
48 rdf:rest Ndf6f67240da94704b5c77d33ee2be745
49 N35b7e273da514897b9ae47ae7c972900 schema:name Springer Nature - SN SciGraph project
50 rdf:type schema:Organization
51 N401448903b1e4090bf87d8eba8ec10a0 schema:isbn 978-3-540-40493-4
52 978-3-540-45061-0
53 schema:name Automata, Languages and Programming
54 rdf:type schema:Book
55 N4b323987e323477b9648ac30507d0d8b rdf:first sg:person.010145160357.51
56 rdf:rest Nfb02d48d58bb4006943ecad3c87aff96
57 N5dc79bcf002741f68033b67c53423fb6 rdf:first Nb68616d810374aaabf36d94aea9ff383
58 rdf:rest N33127af5a7a840d08c16c5c777fc0f89
59 N5f9a4c6791d4453e9484e859e5a29feb rdf:first sg:person.07475505355.50
60 rdf:rest Nf0f54b3325e64c7ebf687a1f44b5a840
61 N6bfb674d67ea4975b17cfa011b622f1d rdf:first N29bc57e730424ba2a44cf8226478429b
62 rdf:rest N5dc79bcf002741f68033b67c53423fb6
63 N79073b3b3d9a470f9004c8ed9b10ff17 schema:familyName Parrow
64 schema:givenName Joachim
65 rdf:type schema:Person
66 Nb68616d810374aaabf36d94aea9ff383 schema:familyName Lenstra
67 schema:givenName Jan Karel
68 rdf:type schema:Person
69 Ndf6f67240da94704b5c77d33ee2be745 rdf:first N235e665a809841b78613108af0adaacd
70 rdf:rest rdf:nil
71 Ndf732132db19479293db67e588f74ff6 schema:name dimensions_id
72 schema:value pub.1031082725
73 rdf:type schema:PropertyValue
74 Ne834d914c99a4f50b4d896e6aa9257ee schema:name readcube_id
75 schema:value 94133630bed447fd5d4c5e2a6c435389d8768a64d075bc8bccc639d8a14b3bda
76 rdf:type schema:PropertyValue
77 Nf0f54b3325e64c7ebf687a1f44b5a840 rdf:first sg:person.011355176201.51
78 rdf:rest N4b323987e323477b9648ac30507d0d8b
79 Nf39e1cc8465648f380ed57aa942828de schema:location Berlin, Heidelberg
80 schema:name Springer Berlin Heidelberg
81 rdf:type schema:Organisation
82 Nfb02d48d58bb4006943ecad3c87aff96 rdf:first sg:person.013624103516.76
83 rdf:rest N04a3b4932eb84d409b5b29aa8801320e
84 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
85 schema:name Information and Computing Sciences
86 rdf:type schema:DefinedTerm
87 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
88 schema:name Computation Theory and Mathematics
89 rdf:type schema:DefinedTerm
90 sg:grant.3750114 http://pending.schema.org/fundedItem sg:pub.10.1007/3-540-45061-0_85
91 rdf:type schema:MonetaryGrant
92 sg:person.010145160357.51 schema:affiliation https://www.grid.ac/institutes/grid.8509.4
93 schema:familyName Nicosia
94 schema:givenName Gaia
95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010145160357.51
96 rdf:type schema:Person
97 sg:person.011355176201.51 schema:affiliation https://www.grid.ac/institutes/grid.6530.0
98 schema:familyName Gambosi
99 schema:givenName Giorgio
100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011355176201.51
101 rdf:type schema:Person
102 sg:person.013624103516.76 schema:affiliation https://www.grid.ac/institutes/grid.11780.3f
103 schema:familyName Penna
104 schema:givenName Paolo
105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013624103516.76
106 rdf:type schema:Person
107 sg:person.016230612433.51 schema:affiliation https://www.grid.ac/institutes/grid.1957.a
108 schema:familyName Unger
109 schema:givenName Walter
110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016230612433.51
111 rdf:type schema:Person
112 sg:person.07475505355.50 schema:affiliation https://www.grid.ac/institutes/grid.8404.8
113 schema:familyName Crescenzi
114 schema:givenName Pilu
115 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07475505355.50
116 rdf:type schema:Person
117 sg:pub.10.1007/bf01585745 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006292857
118 https://doi.org/10.1007/bf01585745
119 rdf:type schema:CreativeWork
120 sg:pub.10.1007/bf01918335 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028360600
121 https://doi.org/10.1007/bf01918335
122 rdf:type schema:CreativeWork
123 sg:pub.10.1007/pl00009214 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007091005
124 https://doi.org/10.1007/pl00009214
125 rdf:type schema:CreativeWork
126 https://doi.org/10.1006/jagm.1995.0799 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015422383
127 rdf:type schema:CreativeWork
128 https://doi.org/10.1006/jagm.1995.1008 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034855085
129 rdf:type schema:CreativeWork
130 https://doi.org/10.1016/0041-1647(70)90196-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032750498
131 rdf:type schema:CreativeWork
132 https://doi.org/10.1016/0304-3975(94)90153-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012616905
133 rdf:type schema:CreativeWork
134 https://doi.org/10.1016/s0020-0190(97)00085-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003156187
135 rdf:type schema:CreativeWork
136 https://doi.org/10.1137/s0097539798346135 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062880285
137 rdf:type schema:CreativeWork
138 https://www.grid.ac/institutes/grid.11780.3f schema:alternateName University of Salerno
139 schema:name Dipartimento di Informatica ed Applicazioni “R.M. Capocelli”, Università di Salerno, via S. Allende 2, I-84081 Baronissi (SA), Italy
140 rdf:type schema:Organization
141 https://www.grid.ac/institutes/grid.1957.a schema:alternateName RWTH Aachen University
142 schema:name RWTH Aachen, Ahornstrasse 55, 52056 Aachen, Germany
143 rdf:type schema:Organization
144 https://www.grid.ac/institutes/grid.6530.0 schema:alternateName University of Rome Tor Vergata
145 schema:name Dipartimento di Matematica, Università di Roma “Tor Vergata”, via della Ricerca Scientifica, I-00133 Roma, Italy
146 rdf:type schema:Organization
147 https://www.grid.ac/institutes/grid.8404.8 schema:alternateName University of Florence
148 schema:name Dipartimento di Sistemi ed Informatica, Università di Firenze, via C. Lombroso 6/17, I-50134 Firenze, Italy
149 rdf:type schema:Organization
150 https://www.grid.ac/institutes/grid.8509.4 schema:alternateName Roma Tre University
151 schema:name Dipartimento di Informatica e Automazione, Università degli studi “Roma Tre”, via della Vasca Navale 79, I-00146 Roma, Italy
152 rdf:type schema:Organization
 




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


...