An Equivalent Version of the Caccetta-Häggkvist Conjecture in an Online Load Balancing Problem View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2007

AUTHORS

Angelo Monti , Paolo Penna , Riccardo Silvestri

ABSTRACT

We study the competitive ratio of certain online algorithms for a well-studied class of load balancing problems. These algorithms are obtained and analyzed according to a method by Crescenzi et al (2004). We show that an exact analysis of their competitive ratio on certain “uniform” instances would resolve a fundamental conjecture by Caccetta and Häggkvist (1978). The conjecture is that any digraph on n nodes and minimum outdegree d must contain a directed cycle involving at most ⌈n/d ⌉ nodes. Our results are the first relating this conjecture to the competitive analysis of certain algorithms, thus suggesting a new approach to the conjecture itself. We also prove that, on “uniform” instances, the analysis by Crescenzi et al (2004) gives only trivial upper bounds, unless we find a counterexample to the conjecture. This is in contrast with other (notable) examples where the same analysis yields optimal (non-trivial) bounds. More... »

PAGES

154-165

Book

TITLE

Graph-Theoretic Concepts in Computer Science

ISBN

978-3-540-74838-0

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-74839-7_16

DOI

http://dx.doi.org/10.1007/978-3-540-74839-7_16

DIMENSIONS

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


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/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Sapienza University of Rome", 
          "id": "https://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "Dipartimento di Informatica, Universit\u00e0 degli Studi di Roma \u201cLa Sapienza\u201d, via Salaria 113, Roma, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Monti", 
        "givenName": "Angelo", 
        "id": "sg:person.013471123531.02", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013471123531.02"
        ], 
        "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, Baronissi (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": "Sapienza University of Rome", 
          "id": "https://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "Dipartimento di Informatica, Universit\u00e0 degli Studi di Roma \u201cLa Sapienza\u201d, via Salaria 113, Roma, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Silvestri", 
        "givenName": "Riccardo", 
        "id": "sg:person.012430640403.64", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012430640403.64"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1006/jctb.1998.1839", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1003930609"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1112/jlms/s1-36.1.445", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008817827"
        ], 
        "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/11558989_2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025382858", 
          "https://doi.org/10.1007/11558989_2"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11558989_2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025382858", 
          "https://doi.org/10.1007/11558989_2"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bfb0029569", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032724318", 
          "https://doi.org/10.1007/bfb0029569"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s003730200048", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1034053234", 
          "https://doi.org/10.1007/s003730200048"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.jda.2006.02.001", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1040779482"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s0097539798346135", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062880285"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.4064/fm-69-3-227-231", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1091799705"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2007", 
    "datePublishedReg": "2007-01-01", 
    "description": "We study the competitive ratio of certain online algorithms for a well-studied class of load balancing problems. These algorithms are obtained and analyzed according to a method by Crescenzi et al (2004). We show that an exact analysis of their competitive ratio on certain \u201cuniform\u201d instances would resolve a fundamental conjecture by Caccetta and H\u00e4ggkvist (1978). The conjecture is that any digraph on n nodes and minimum outdegree d must contain a directed cycle involving at most \u2308n/d \u2309 nodes. Our results are the first relating this conjecture to the competitive analysis of certain algorithms, thus suggesting a new approach to the conjecture itself. We also prove that, on \u201cuniform\u201d instances, the analysis by Crescenzi et al (2004) gives only trivial upper bounds, unless we find a counterexample to the conjecture. This is in contrast with other (notable) examples where the same analysis yields optimal (non-trivial) bounds.", 
    "editor": [
      {
        "familyName": "Brandst\u00e4dt", 
        "givenName": "Andreas", 
        "type": "Person"
      }, 
      {
        "familyName": "Kratsch", 
        "givenName": "Dieter", 
        "type": "Person"
      }, 
      {
        "familyName": "M\u00fcller", 
        "givenName": "Haiko", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-74839-7_16", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-74838-0"
      ], 
      "name": "Graph-Theoretic Concepts in Computer Science", 
      "type": "Book"
    }, 
    "name": "An Equivalent Version of the Caccetta-H\u00e4ggkvist Conjecture in an Online Load Balancing Problem", 
    "pagination": "154-165", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-74839-7_16"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "c16cb755e382825828f74ea495f0a7c5653f18588971998d78a999ca2f643855"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1040604486"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-74839-7_16", 
      "https://app.dimensions.ai/details/publication/pub.1040604486"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T05:40", 
    "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/0000000347_0000000347/records_89785_00000001.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-3-540-74839-7_16"
  }
]
 

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/978-3-540-74839-7_16'

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/978-3-540-74839-7_16'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-74839-7_16'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-74839-7_16'


 

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

124 TRIPLES      23 PREDICATES      37 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-74839-7_16 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N8e8493be7e2848e9b2b1eb9fc0a80869
4 schema:citation sg:pub.10.1007/11558989_2
5 sg:pub.10.1007/bfb0029569
6 sg:pub.10.1007/s003730200048
7 https://doi.org/10.1006/jagm.1995.0799
8 https://doi.org/10.1006/jctb.1998.1839
9 https://doi.org/10.1016/0304-3975(94)90153-8
10 https://doi.org/10.1016/j.jda.2006.02.001
11 https://doi.org/10.1112/jlms/s1-36.1.445
12 https://doi.org/10.1137/s0097539798346135
13 https://doi.org/10.4064/fm-69-3-227-231
14 schema:datePublished 2007
15 schema:datePublishedReg 2007-01-01
16 schema:description We study the competitive ratio of certain online algorithms for a well-studied class of load balancing problems. These algorithms are obtained and analyzed according to a method by Crescenzi et al (2004). We show that an exact analysis of their competitive ratio on certain “uniform” instances would resolve a fundamental conjecture by Caccetta and Häggkvist (1978). The conjecture is that any digraph on n nodes and minimum outdegree d must contain a directed cycle involving at most ⌈n/d ⌉ nodes. Our results are the first relating this conjecture to the competitive analysis of certain algorithms, thus suggesting a new approach to the conjecture itself. We also prove that, on “uniform” instances, the analysis by Crescenzi et al (2004) gives only trivial upper bounds, unless we find a counterexample to the conjecture. This is in contrast with other (notable) examples where the same analysis yields optimal (non-trivial) bounds.
17 schema:editor Nf36f6df46b2048caa5e2f58e3f717c39
18 schema:genre chapter
19 schema:inLanguage en
20 schema:isAccessibleForFree false
21 schema:isPartOf Nee4af02f3cd443118aad9d7f17e258e9
22 schema:name An Equivalent Version of the Caccetta-Häggkvist Conjecture in an Online Load Balancing Problem
23 schema:pagination 154-165
24 schema:productId N5f3870fda1ce4c9fb3f2d0a33a62e73c
25 N763139c1928b4c7780dc5f431d01a4ec
26 Naa86ef686ba54bdcaa85e7d405efd489
27 schema:publisher N31c9dd2ac49a49deb1a1129bc56b3fb7
28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040604486
29 https://doi.org/10.1007/978-3-540-74839-7_16
30 schema:sdDatePublished 2019-04-16T05:40
31 schema:sdLicense https://scigraph.springernature.com/explorer/license/
32 schema:sdPublisher N1d613281b9fb48f99d822b7ec471543d
33 schema:url https://link.springer.com/10.1007%2F978-3-540-74839-7_16
34 sgo:license sg:explorer/license/
35 sgo:sdDataset chapters
36 rdf:type schema:Chapter
37 N052073de44f146fcb9429b3ba2f791d9 schema:familyName Kratsch
38 schema:givenName Dieter
39 rdf:type schema:Person
40 N1d613281b9fb48f99d822b7ec471543d schema:name Springer Nature - SN SciGraph project
41 rdf:type schema:Organization
42 N1e71d0a6fdb947418446f4b735c4f4a8 rdf:first N052073de44f146fcb9429b3ba2f791d9
43 rdf:rest N23503090485642e5a9be0cabf8c95c52
44 N23503090485642e5a9be0cabf8c95c52 rdf:first Nf697a95355114693924a9bb5bab7580c
45 rdf:rest rdf:nil
46 N31c9dd2ac49a49deb1a1129bc56b3fb7 schema:location Berlin, Heidelberg
47 schema:name Springer Berlin Heidelberg
48 rdf:type schema:Organisation
49 N4bf25af1af1544b7b7e6113227247fd8 rdf:first sg:person.013624103516.76
50 rdf:rest Ne437c9ecd187434195c3cdfde982ba70
51 N5f3870fda1ce4c9fb3f2d0a33a62e73c schema:name dimensions_id
52 schema:value pub.1040604486
53 rdf:type schema:PropertyValue
54 N70dd1ac71a6b4a96899342ab325bf6c1 schema:familyName Brandstädt
55 schema:givenName Andreas
56 rdf:type schema:Person
57 N763139c1928b4c7780dc5f431d01a4ec schema:name readcube_id
58 schema:value c16cb755e382825828f74ea495f0a7c5653f18588971998d78a999ca2f643855
59 rdf:type schema:PropertyValue
60 N8e8493be7e2848e9b2b1eb9fc0a80869 rdf:first sg:person.013471123531.02
61 rdf:rest N4bf25af1af1544b7b7e6113227247fd8
62 Naa86ef686ba54bdcaa85e7d405efd489 schema:name doi
63 schema:value 10.1007/978-3-540-74839-7_16
64 rdf:type schema:PropertyValue
65 Ne437c9ecd187434195c3cdfde982ba70 rdf:first sg:person.012430640403.64
66 rdf:rest rdf:nil
67 Nee4af02f3cd443118aad9d7f17e258e9 schema:isbn 978-3-540-74838-0
68 schema:name Graph-Theoretic Concepts in Computer Science
69 rdf:type schema:Book
70 Nf36f6df46b2048caa5e2f58e3f717c39 rdf:first N70dd1ac71a6b4a96899342ab325bf6c1
71 rdf:rest N1e71d0a6fdb947418446f4b735c4f4a8
72 Nf697a95355114693924a9bb5bab7580c schema:familyName Müller
73 schema:givenName Haiko
74 rdf:type schema:Person
75 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
76 schema:name Mathematical Sciences
77 rdf:type schema:DefinedTerm
78 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
79 schema:name Pure Mathematics
80 rdf:type schema:DefinedTerm
81 sg:person.012430640403.64 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
82 schema:familyName Silvestri
83 schema:givenName Riccardo
84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012430640403.64
85 rdf:type schema:Person
86 sg:person.013471123531.02 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
87 schema:familyName Monti
88 schema:givenName Angelo
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013471123531.02
90 rdf:type schema:Person
91 sg:person.013624103516.76 schema:affiliation https://www.grid.ac/institutes/grid.11780.3f
92 schema:familyName Penna
93 schema:givenName Paolo
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013624103516.76
95 rdf:type schema:Person
96 sg:pub.10.1007/11558989_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025382858
97 https://doi.org/10.1007/11558989_2
98 rdf:type schema:CreativeWork
99 sg:pub.10.1007/bfb0029569 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032724318
100 https://doi.org/10.1007/bfb0029569
101 rdf:type schema:CreativeWork
102 sg:pub.10.1007/s003730200048 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034053234
103 https://doi.org/10.1007/s003730200048
104 rdf:type schema:CreativeWork
105 https://doi.org/10.1006/jagm.1995.0799 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015422383
106 rdf:type schema:CreativeWork
107 https://doi.org/10.1006/jctb.1998.1839 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003930609
108 rdf:type schema:CreativeWork
109 https://doi.org/10.1016/0304-3975(94)90153-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012616905
110 rdf:type schema:CreativeWork
111 https://doi.org/10.1016/j.jda.2006.02.001 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040779482
112 rdf:type schema:CreativeWork
113 https://doi.org/10.1112/jlms/s1-36.1.445 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008817827
114 rdf:type schema:CreativeWork
115 https://doi.org/10.1137/s0097539798346135 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062880285
116 rdf:type schema:CreativeWork
117 https://doi.org/10.4064/fm-69-3-227-231 schema:sameAs https://app.dimensions.ai/details/publication/pub.1091799705
118 rdf:type schema:CreativeWork
119 https://www.grid.ac/institutes/grid.11780.3f schema:alternateName University of Salerno
120 schema:name Dipartimento di Informatica ed Applicazioni “R.M. Capocelli”, Università di Salerno, via S. Allende 2, Baronissi (SA), Italy
121 rdf:type schema:Organization
122 https://www.grid.ac/institutes/grid.7841.a schema:alternateName Sapienza University of Rome
123 schema:name Dipartimento di Informatica, Università degli Studi di Roma “La Sapienza”, via Salaria 113, Roma, Italy
124 rdf:type schema:Organization
 




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


...