Name
Title | ||
|---|---|---|
An equivalent version of the Caccetta-Häggkvist conjecture in an online load balancing problem |
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. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/978-3-540-74839-7_16 | WG |
Keywords | Field | DocType |
fundamental conjecture,minimum outdegree,equivalent version,n node,competitive ratio,exact analysis,competitive analysis,certain algorithm,new approach,online load,analysis yields optimal,certain online algorithm,ggkvist conjecture,upper bound,online algorithm,load balance | Online algorithm,Discrete mathematics,Combinatorics,Load balancing (computing),Counterexample,Collatz conjecture,Conjecture,Mathematics,Digraph,Competitive analysis | Conference |
Volume | ISSN | ISBN |
4769 | 0302-9743 | 3-540-74838-5 |
Citations | PageRank | References |
1 | 0.36 | 8 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Angelo Monti | 1 | 671 | 46.93 |
| Paolo Penna | 2 | 202 | 16.42 |
| Riccardo Silvestri | 3 | 1324 | 90.84 |