Name
Abstract | ||
|---|---|---|
The online CNN problem had no known competitive algorithms for a long time. Sitters, Stougie and de Paepe showed that there exists a competitive online algorithm for this problem. However, both their algorithm and analysis are quite complicated, and above all, their upper bound for the competitive ratio is 105. In this paper, we examine why this problem seems so difficult. To this end we introduce a nontrivial restriction, orthogonality, against this problem and show that it decreases the competitive ratio dramatically, down to at most 9. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1016/j.ipl.2004.01.022 | Inf. Process. Lett. |
Keywords | Field | DocType |
competitive algorithm,competitive ratio,online cnn problem,long time,nontrivial restriction,orthogonal cnn problem,competitive online algorithm,de paepe,upper bound,competitive analysis,online algorithm | Online algorithm,Discrete mathematics,Information processing,Existential quantification,Upper and lower bounds,Orthogonality,Mathematics,Competitive analysis | Journal |
Volume | Issue | ISSN |
90 | 3 | 0020-0190 |
Citations | PageRank | References |
4 | 0.45 | 6 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kazuo Iwama | 1 | 1400 | 153.38 |
| Kouki Yonezawa | 2 | 17 | 4.05 |