תקציר
This paper is concerned with online caching algorithms for the (n,k)-companion cache, defined by Brehob et al. (J. Scheduling 6 (2003) 149). In this model the cache is composed of two components: a k-way set-associative cache and a companion fully associative cache of size n. We show that the deterministic competitive ratio for this problem is (n+1)(k+1)-1, and the randomized competitive ratio is O(lognlogk) and Ω(logn+logk).
| שפה מקורית | אנגלית |
|---|---|
| עמודים (מ-עד) | 183-200 |
| מספר עמודים | 18 |
| כתב עת | Theoretical Computer Science |
| כרך | 324 |
| מספר גיליון | 2-3 SPEC. ISS. |
| מזהי עצם דיגיטלי (DOIs) | |
| סטטוס פרסום | פורסם - 20 ספט׳ 2004 |
| פורסם באופן חיצוני | כן |
הערה ביבליוגרפית
Funding Information:Preliminary version of this paper appeared in [7]. ∗Corresponding author. E-mail address: [email protected] (M. Mendel). 1The 'rst named author would like to dedicate this paper in memory of Steven Seiden. 2Partially supported by the Louisiana Board of Regents Research Competitiveness Subprogram