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

References to SciGraph publications

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 Nbafb716626f04b27906c99210e110cea
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 N45bf971816be4651bfb47d734782457a
40 N7b4724a80a4c4bbd828f1e2a80f4c467
41 sg:journal.1047644
42 schema:name Tight Bounds for Selfish and Greedy Load Balancing
43 schema:pagination 606-637
44 schema:productId N1c1a34bf5a0a44fca8c9e36b92605d05
45 N8902d6acf4d04daf93f1f53465f436c5
46 Ncc34efba7d1c4907b3744695476aea80
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 N11f5d5568362435bb25641f2a0d62003
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 N0fba887b49aa4851a346efb1e8b15aaa rdf:first sg:person.014117131215.37
57 rdf:rest rdf:nil
58 N11f5d5568362435bb25641f2a0d62003 schema:name Springer Nature - SN SciGraph project
59 rdf:type schema:Organization
60 N1c1a34bf5a0a44fca8c9e36b92605d05 schema:name doi
61 schema:value 10.1007/s00453-010-9427-8
62 rdf:type schema:PropertyValue
63 N45bf971816be4651bfb47d734782457a schema:issueNumber 3
64 rdf:type schema:PublicationIssue
65 N6f00f2487ad04c498282ff8874882c21 rdf:first sg:person.011345131043.86
66 rdf:rest N0fba887b49aa4851a346efb1e8b15aaa
67 N7b4724a80a4c4bbd828f1e2a80f4c467 schema:volumeNumber 61
68 rdf:type schema:PublicationVolume
69 N8902d6acf4d04daf93f1f53465f436c5 schema:name dimensions_id
70 schema:value pub.1016706126
71 rdf:type schema:PropertyValue
72 N8bcf4cd1f4a4495ab5b6029152f1c4a5 rdf:first sg:person.015753166476.90
73 rdf:rest Nde52c3593820495bb8807ecfc41f5037
74 Nbafb716626f04b27906c99210e110cea rdf:first sg:person.015657660643.37
75 rdf:rest N8bcf4cd1f4a4495ab5b6029152f1c4a5
76 Ncc34efba7d1c4907b3744695476aea80 schema:name readcube_id
77 schema:value 4f9922aa6770d1aebfc54357676b45bde13f85939bdb97905acdd3028edf4c6d
78 rdf:type schema:PropertyValue
79 Nde52c3593820495bb8807ecfc41f5037 rdf:first sg:person.015354551107.35
80 rdf:rest N6f00f2487ad04c498282ff8874882c21
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)


...