Tight Bounds for Selfish and Greedy Load Balancing View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2011-11

AUTHORS

Ioannis Caragiannis, Michele Flammini, Christos Kaklamanis, Panagiotis Kanellopoulos, Luca Moscardelli

ABSTRACT

We study the load balancing problem in the context of a set of clients each wishing to run a job on a server selected among a subset of permissible servers for the particular client. We consider two different scenarios. In selfish load balancing, each client is selfish in the sense that it chooses, among its permissible servers, to run its job on the server having the smallest latency given the assignments of the jobs of other clients to servers. In online load balancing, clients appear online and, when a client appears, it has to make an irrevocable decision and assign its job to one of its permissible servers. Here, we assume that the clients aim to optimize some global criterion but in an online fashion. A natural local optimization criterion that can be used by each client when making its decision is to assign its job to that server that gives the minimum increase of the global objective. This gives rise to greedy online solutions. The aim of this paper is to determine how much the quality of load balancing is affected by selfishness and greediness. We characterize almost completely the impact of selfishness and greediness in load balancing by presenting new and improved, tight or almost tight bounds on the price of anarchy of selfish load balancing as well as on the competitiveness of the greedy algorithm for online load balancing when the objective is to minimize the total latency of all clients on servers with linear latency functions. In addition, we prove a tight upper bound on the price of stability of linear congestion games. More... »

PAGES

606-637

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00453-010-9427-8

DOI

http://dx.doi.org/10.1007/s00453-010-9427-8

DIMENSIONS

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


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/0806", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information Systems", 
        "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 Patras", 
          "id": "https://www.grid.ac/institutes/grid.11047.33", 
          "name": [
            "Research Academic Computer Technology Institute & Department of Computer Engineering and Informatics, University of Patras, 26500, Rio, Greece"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Caragiannis", 
        "givenName": "Ioannis", 
        "id": "sg:person.015657660643.37", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015657660643.37"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of L'Aquila", 
          "id": "https://www.grid.ac/institutes/grid.158820.6", 
          "name": [
            "Dipartimento di Informatica, Universit\u00e0 di L\u2019Aquila, Via Vetoio, 67100, Coppito, L\u2019Aquila, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Flammini", 
        "givenName": "Michele", 
        "id": "sg:person.015753166476.90", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015753166476.90"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Patras", 
          "id": "https://www.grid.ac/institutes/grid.11047.33", 
          "name": [
            "Research Academic Computer Technology Institute & Department of Computer Engineering and Informatics, University of Patras, 26500, Rio, Greece"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kaklamanis", 
        "givenName": "Christos", 
        "id": "sg:person.015354551107.35", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015354551107.35"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Patras", 
          "id": "https://www.grid.ac/institutes/grid.11047.33", 
          "name": [
            "Research Academic Computer Technology Institute & Department of Computer Engineering and Informatics, University of Patras, 26500, Rio, Greece"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kanellopoulos", 
        "givenName": "Panagiotis", 
        "id": "sg:person.011345131043.86", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011345131043.86"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Chieti-Pescara", 
          "id": "https://www.grid.ac/institutes/grid.412451.7", 
          "name": [
            "Department of Sciences, University of Chieti-Pescara, Viale Pindaro 42, 65127, Pescara, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Moscardelli", 
        "givenName": "Luca", 
        "id": "sg:person.014117131215.37", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014117131215.37"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1145/167088.167201", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000682821"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.geb.2003.06.004", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1001396666"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.geb.2003.06.004", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1001396666"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-49116-3_38", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1002207134", 
          "https://doi.org/10.1007/3-540-49116-3_38"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-49116-3_38", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1002207134", 
          "https://doi.org/10.1007/3-540-49116-3_38"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/506147.506153", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1002416680"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s004530010051", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006821977", 
          "https://doi.org/10.1007/s004530010051"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.tcs.2008.01.004", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009758545"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.tcs.2008.06.045", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013590738"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11786986_46", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014686057", 
          "https://doi.org/10.1007/11786986_46"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11786986_46", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014686057", 
          "https://doi.org/10.1007/11786986_46"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/321921.321933", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1015834090"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00224-003-1131-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017670693", 
          "https://doi.org/10.1007/s00224-003-1131-5"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1186810.1186814", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017783227"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/380752.380883", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018290072"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-006-1211-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1022756805", 
          "https://doi.org/10.1007/s00453-006-1211-4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1060590.1060639", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025774284"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11672142_17", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026310762", 
          "https://doi.org/10.1007/11672142_17"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11672142_17", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026310762", 
          "https://doi.org/10.1007/11672142_17"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1060590.1060599", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1029757185"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1007352.1007446", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1029949463"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-006-0056-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035808115", 
          "https://doi.org/10.1007/s00453-006-0056-1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.tcs.2005.09.024", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035891562"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.tcs.2005.09.024", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035891562"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.jcss.2008.07.001", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1042525379"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11672142_28", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1042916113", 
          "https://doi.org/10.1007/11672142_28"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11672142_28", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1042916113", 
          "https://doi.org/10.1007/11672142_28"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01737559", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1044775936", 
          "https://doi.org/10.1007/bf01737559"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.tcs.2006.07.055", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045349637"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1006/game.1996.0044", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048802310"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11561071_8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049866450", 
          "https://doi.org/10.1007/11561071_8"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11561071_8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049866450", 
          "https://doi.org/10.1007/11561071_8"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11561071_8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049866450", 
          "https://doi.org/10.1007/11561071_8"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1060590.1060600", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1050456256"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0204021", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841261"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/070680096", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062850841"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s0097539793248317", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062879822"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2011-11", 
    "datePublishedReg": "2011-11-01", 
    "description": "We study the load balancing problem in the context of a set of clients each wishing to run a job on a server selected among a subset of permissible servers for the particular client. We consider two different scenarios. In selfish load balancing, each client is selfish in the sense that it chooses, among its permissible servers, to run its job on the server having the smallest latency given the assignments of the jobs of other clients to servers. In online load balancing, clients appear online and, when a client appears, it has to make an irrevocable decision and assign its job to one of its permissible servers. Here, we assume that the clients aim to optimize some global criterion but in an online fashion. A natural local optimization criterion that can be used by each client when making its decision is to assign its job to that server that gives the minimum increase of the global objective. This gives rise to greedy online solutions. The aim of this paper is to determine how much the quality of load balancing is affected by selfishness and greediness. We characterize almost completely the impact of selfishness and greediness in load balancing by presenting new and improved, tight or almost tight bounds on the price of anarchy of selfish load balancing as well as on the competitiveness of the greedy algorithm for online load balancing when the objective is to minimize the total latency of all clients on servers with linear latency functions. In addition, we prove a tight upper bound on the price of stability of linear congestion games.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s00453-010-9427-8", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1047644", 
        "issn": [
          "0178-4617", 
          "1432-0541"
        ], 
        "name": "Algorithmica", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "3", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "61"
      }
    ], 
    "name": "Tight Bounds for Selfish and Greedy Load Balancing", 
    "pagination": "606-637", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "4f9922aa6770d1aebfc54357676b45bde13f85939bdb97905acdd3028edf4c6d"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00453-010-9427-8"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1016706126"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00453-010-9427-8", 
      "https://app.dimensions.ai/details/publication/pub.1016706126"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-10T21:36", 
    "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_8687_00000511.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007%2Fs00453-010-9427-8"
  }
]
 

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/s00453-010-9427-8'

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/s00453-010-9427-8'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-010-9427-8'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-010-9427-8'


 

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

192 TRIPLES      21 PREDICATES      56 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00453-010-9427-8 schema:about anzsrc-for:08
2 anzsrc-for:0806
3 schema:author N973e00e59d744521a429c6afc3e8178b
4 schema:citation sg:pub.10.1007/11561071_8
5 sg:pub.10.1007/11672142_17
6 sg:pub.10.1007/11672142_28
7 sg:pub.10.1007/11786986_46
8 sg:pub.10.1007/3-540-49116-3_38
9 sg:pub.10.1007/bf01737559
10 sg:pub.10.1007/s00224-003-1131-5
11 sg:pub.10.1007/s00453-006-0056-1
12 sg:pub.10.1007/s00453-006-1211-4
13 sg:pub.10.1007/s004530010051
14 https://doi.org/10.1006/game.1996.0044
15 https://doi.org/10.1016/j.geb.2003.06.004
16 https://doi.org/10.1016/j.jcss.2008.07.001
17 https://doi.org/10.1016/j.tcs.2005.09.024
18 https://doi.org/10.1016/j.tcs.2006.07.055
19 https://doi.org/10.1016/j.tcs.2008.01.004
20 https://doi.org/10.1016/j.tcs.2008.06.045
21 https://doi.org/10.1137/0204021
22 https://doi.org/10.1137/070680096
23 https://doi.org/10.1137/s0097539793248317
24 https://doi.org/10.1145/1007352.1007446
25 https://doi.org/10.1145/1060590.1060599
26 https://doi.org/10.1145/1060590.1060600
27 https://doi.org/10.1145/1060590.1060639
28 https://doi.org/10.1145/1186810.1186814
29 https://doi.org/10.1145/167088.167201
30 https://doi.org/10.1145/321921.321933
31 https://doi.org/10.1145/380752.380883
32 https://doi.org/10.1145/506147.506153
33 schema:datePublished 2011-11
34 schema:datePublishedReg 2011-11-01
35 schema:description We study the load balancing problem in the context of a set of clients each wishing to run a job on a server selected among a subset of permissible servers for the particular client. We consider two different scenarios. In selfish load balancing, each client is selfish in the sense that it chooses, among its permissible servers, to run its job on the server having the smallest latency given the assignments of the jobs of other clients to servers. In online load balancing, clients appear online and, when a client appears, it has to make an irrevocable decision and assign its job to one of its permissible servers. Here, we assume that the clients aim to optimize some global criterion but in an online fashion. A natural local optimization criterion that can be used by each client when making its decision is to assign its job to that server that gives the minimum increase of the global objective. This gives rise to greedy online solutions. The aim of this paper is to determine how much the quality of load balancing is affected by selfishness and greediness. We characterize almost completely the impact of selfishness and greediness in load balancing by presenting new and improved, tight or almost tight bounds on the price of anarchy of selfish load balancing as well as on the competitiveness of the greedy algorithm for online load balancing when the objective is to minimize the total latency of all clients on servers with linear latency functions. In addition, we prove a tight upper bound on the price of stability of linear congestion games.
36 schema:genre research_article
37 schema:inLanguage en
38 schema:isAccessibleForFree false
39 schema:isPartOf N2cdb4ca2c81b4e4ea8750802bca9267c
40 Ncc89ebfd261744b2b32f13d24b8fa67b
41 sg:journal.1047644
42 schema:name Tight Bounds for Selfish and Greedy Load Balancing
43 schema:pagination 606-637
44 schema:productId N44792aa65abb4d2cbff8510ad245beb7
45 Nabd333b9f9bf49219a1995f884bbd7f8
46 Nc79fd86394544fc7818de56c79ed9b42
47 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016706126
48 https://doi.org/10.1007/s00453-010-9427-8
49 schema:sdDatePublished 2019-04-10T21:36
50 schema:sdLicense https://scigraph.springernature.com/explorer/license/
51 schema:sdPublisher Ne0e7d1a96b4f407b8f29120f071a4d8a
52 schema:url http://link.springer.com/10.1007%2Fs00453-010-9427-8
53 sgo:license sg:explorer/license/
54 sgo:sdDataset articles
55 rdf:type schema:ScholarlyArticle
56 N0a1576932b2c4e4aa53e680a78db5f67 rdf:first sg:person.011345131043.86
57 rdf:rest N96b477e95302457dbcd6d0e494591fb6
58 N0b6626ab6cee4ee38133a9de803f3f50 rdf:first sg:person.015753166476.90
59 rdf:rest N143f9ee7bbc140e69c34e430a35495e5
60 N143f9ee7bbc140e69c34e430a35495e5 rdf:first sg:person.015354551107.35
61 rdf:rest N0a1576932b2c4e4aa53e680a78db5f67
62 N2cdb4ca2c81b4e4ea8750802bca9267c schema:volumeNumber 61
63 rdf:type schema:PublicationVolume
64 N44792aa65abb4d2cbff8510ad245beb7 schema:name dimensions_id
65 schema:value pub.1016706126
66 rdf:type schema:PropertyValue
67 N96b477e95302457dbcd6d0e494591fb6 rdf:first sg:person.014117131215.37
68 rdf:rest rdf:nil
69 N973e00e59d744521a429c6afc3e8178b rdf:first sg:person.015657660643.37
70 rdf:rest N0b6626ab6cee4ee38133a9de803f3f50
71 Nabd333b9f9bf49219a1995f884bbd7f8 schema:name doi
72 schema:value 10.1007/s00453-010-9427-8
73 rdf:type schema:PropertyValue
74 Nc79fd86394544fc7818de56c79ed9b42 schema:name readcube_id
75 schema:value 4f9922aa6770d1aebfc54357676b45bde13f85939bdb97905acdd3028edf4c6d
76 rdf:type schema:PropertyValue
77 Ncc89ebfd261744b2b32f13d24b8fa67b schema:issueNumber 3
78 rdf:type schema:PublicationIssue
79 Ne0e7d1a96b4f407b8f29120f071a4d8a schema:name Springer Nature - SN SciGraph project
80 rdf:type schema:Organization
81 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
82 schema:name Information and Computing Sciences
83 rdf:type schema:DefinedTerm
84 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
85 schema:name Information Systems
86 rdf:type schema:DefinedTerm
87 sg:journal.1047644 schema:issn 0178-4617
88 1432-0541
89 schema:name Algorithmica
90 rdf:type schema:Periodical
91 sg:person.011345131043.86 schema:affiliation https://www.grid.ac/institutes/grid.11047.33
92 schema:familyName Kanellopoulos
93 schema:givenName Panagiotis
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011345131043.86
95 rdf:type schema:Person
96 sg:person.014117131215.37 schema:affiliation https://www.grid.ac/institutes/grid.412451.7
97 schema:familyName Moscardelli
98 schema:givenName Luca
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014117131215.37
100 rdf:type schema:Person
101 sg:person.015354551107.35 schema:affiliation https://www.grid.ac/institutes/grid.11047.33
102 schema:familyName Kaklamanis
103 schema:givenName Christos
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015354551107.35
105 rdf:type schema:Person
106 sg:person.015657660643.37 schema:affiliation https://www.grid.ac/institutes/grid.11047.33
107 schema:familyName Caragiannis
108 schema:givenName Ioannis
109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015657660643.37
110 rdf:type schema:Person
111 sg:person.015753166476.90 schema:affiliation https://www.grid.ac/institutes/grid.158820.6
112 schema:familyName Flammini
113 schema:givenName Michele
114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015753166476.90
115 rdf:type schema:Person
116 sg:pub.10.1007/11561071_8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049866450
117 https://doi.org/10.1007/11561071_8
118 rdf:type schema:CreativeWork
119 sg:pub.10.1007/11672142_17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026310762
120 https://doi.org/10.1007/11672142_17
121 rdf:type schema:CreativeWork
122 sg:pub.10.1007/11672142_28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042916113
123 https://doi.org/10.1007/11672142_28
124 rdf:type schema:CreativeWork
125 sg:pub.10.1007/11786986_46 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014686057
126 https://doi.org/10.1007/11786986_46
127 rdf:type schema:CreativeWork
128 sg:pub.10.1007/3-540-49116-3_38 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002207134
129 https://doi.org/10.1007/3-540-49116-3_38
130 rdf:type schema:CreativeWork
131 sg:pub.10.1007/bf01737559 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044775936
132 https://doi.org/10.1007/bf01737559
133 rdf:type schema:CreativeWork
134 sg:pub.10.1007/s00224-003-1131-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017670693
135 https://doi.org/10.1007/s00224-003-1131-5
136 rdf:type schema:CreativeWork
137 sg:pub.10.1007/s00453-006-0056-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035808115
138 https://doi.org/10.1007/s00453-006-0056-1
139 rdf:type schema:CreativeWork
140 sg:pub.10.1007/s00453-006-1211-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022756805
141 https://doi.org/10.1007/s00453-006-1211-4
142 rdf:type schema:CreativeWork
143 sg:pub.10.1007/s004530010051 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006821977
144 https://doi.org/10.1007/s004530010051
145 rdf:type schema:CreativeWork
146 https://doi.org/10.1006/game.1996.0044 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048802310
147 rdf:type schema:CreativeWork
148 https://doi.org/10.1016/j.geb.2003.06.004 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001396666
149 rdf:type schema:CreativeWork
150 https://doi.org/10.1016/j.jcss.2008.07.001 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042525379
151 rdf:type schema:CreativeWork
152 https://doi.org/10.1016/j.tcs.2005.09.024 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035891562
153 rdf:type schema:CreativeWork
154 https://doi.org/10.1016/j.tcs.2006.07.055 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045349637
155 rdf:type schema:CreativeWork
156 https://doi.org/10.1016/j.tcs.2008.01.004 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009758545
157 rdf:type schema:CreativeWork
158 https://doi.org/10.1016/j.tcs.2008.06.045 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013590738
159 rdf:type schema:CreativeWork
160 https://doi.org/10.1137/0204021 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841261
161 rdf:type schema:CreativeWork
162 https://doi.org/10.1137/070680096 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062850841
163 rdf:type schema:CreativeWork
164 https://doi.org/10.1137/s0097539793248317 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062879822
165 rdf:type schema:CreativeWork
166 https://doi.org/10.1145/1007352.1007446 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029949463
167 rdf:type schema:CreativeWork
168 https://doi.org/10.1145/1060590.1060599 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029757185
169 rdf:type schema:CreativeWork
170 https://doi.org/10.1145/1060590.1060600 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050456256
171 rdf:type schema:CreativeWork
172 https://doi.org/10.1145/1060590.1060639 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025774284
173 rdf:type schema:CreativeWork
174 https://doi.org/10.1145/1186810.1186814 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017783227
175 rdf:type schema:CreativeWork
176 https://doi.org/10.1145/167088.167201 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000682821
177 rdf:type schema:CreativeWork
178 https://doi.org/10.1145/321921.321933 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015834090
179 rdf:type schema:CreativeWork
180 https://doi.org/10.1145/380752.380883 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018290072
181 rdf:type schema:CreativeWork
182 https://doi.org/10.1145/506147.506153 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002416680
183 rdf:type schema:CreativeWork
184 https://www.grid.ac/institutes/grid.11047.33 schema:alternateName University of Patras
185 schema:name Research Academic Computer Technology Institute & Department of Computer Engineering and Informatics, University of Patras, 26500, Rio, Greece
186 rdf:type schema:Organization
187 https://www.grid.ac/institutes/grid.158820.6 schema:alternateName University of L'Aquila
188 schema:name Dipartimento di Informatica, Università di L’Aquila, Via Vetoio, 67100, Coppito, L’Aquila, Italy
189 rdf:type schema:Organization
190 https://www.grid.ac/institutes/grid.412451.7 schema:alternateName University of Chieti-Pescara
191 schema:name Department of Sciences, University of Chieti-Pescara, Viale Pindaro 42, 65127, Pescara, Italy
192 rdf:type schema:Organization
 




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


...