nach oben

Theory of Computing Systems

Erschienen in:

01.01.2015

OnlineMin: A Fast Strongly Competitive Randomized Paging Algorithm

verfasst von: Gerth Stølting Brodal, Gabriel Moruz, Andrei Negoescu

Erschienen in: Theory of Computing Systems | Ausgabe 1/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In the field of online algorithms paging is one of the most studied problems. For randomized paging algorithms a tight bound of H _k on the competitive ratio has been known for decades, yet existing algorithms matching this bound have high running times. We present a new randomized paging algorithm OnlineMin that has optimal competitiveness and allows fast implementations. In fact, if k pages fit in internal memory the best previous solution required O(k ²) time per request and O(k) space. We present two implementations of OnlineMin which use O(k) space, but only O(logk) worst case time and O(logk/loglogk) worst case time per page request respectively.

Vorheriger Artikel On Online Algorithms with Advice for the k-Server Problem

Nächster Artikel Improved Lower Bound for Online Strip Packing

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

In [6] Equitable2 is denoted A _k. Due to its similarity to Equitable we use its original name of Equitable2.

Since no explicit implementation of Equitable2 is provided, due to their similarity we assume it to be the same as for Equitable.

We use a slightly modified, yet equivalent, version of the layer representation in [16].

For easiness of exposition we refer by ω to both the offset function and its corresponding layer representation.

Theorem 1 does not explicitly take into account the forgiveness step. According to Definition 1, if p∈L ₀ and forgiveness is applied we treat p as if it was requested in L ₁.

Achlioptas, D., Chrobak, M., Noga, J.: Competitive analysis of randomized paging algorithms. Theor. Comput. Sci. 234(1–2), 203–218 (2000) CrossRefMATHMathSciNet

Albers, S.: Online algorithms: a survey. Math. Program. 97(1–2), 3–26 (2003) MATHMathSciNet

Alstrup, S., Husfeldt, T., Rauhe, T.: Marked ancestor problems. In: Proc. 39th Annual Symposium on Foundations of Computer Science, pp. 534–544. IEEE Comp. Soc., Los Alamitos (1998)

Andersson, A., Thorup, M.: Dynamic ordered sets with exponential search trees. J. ACM 54(3), 13 (2007) CrossRefMathSciNet

Bayer, R., McCreight, E.: Organization and maintenance of large ordered indexes. Acta Inform. 1(3), 173–189 (1972) CrossRef

Bein, W.W., Larmore, L.L., Noga, J., Reischuk, R.: Knowledge state algorithms. Algorithmica 60(3), 653–678 (2011) CrossRefMATHMathSciNet

Belady, L.A.: A study of replacement algorithms for virtual-storage computer. IBM Syst. J. 5(2), 78–101 (1966) CrossRef

Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, Cambridge (1998) MATH

Chrobak, M., Koutsoupias, E., Noga, J.: More on randomized on-line algorithms for caching. Theor. Comput. Sci. 290(3), 1997–2008 (2003) CrossRefMATHMathSciNet

10.

Fiat, A., Karp, R.M., Luby, M., McGeoch, L.A., Sleator, D.D., Young, N.E.: Competitive paging algorithms. J. Algorithms 12(4), 685–699 (1991) CrossRefMATH

11.

Fiat, A., Woeginger, G.J. (eds.): Online Algorithms, the State of the Art. Lecture Notes in Computer Science, vol. 1442. Springer, Berlin (1998) (the book grow out of a Dagstuhl Seminar, June 1996) MATH

12.

Fisher, R.A., Yates, F.: Statistical Tables for Biological, Agricultural, and Medical Research, 3rd edn. Oliver & Boyd, Edinburgh (1948) MATH

13.

Fredman, M.L., Willard, D.E.: Surpassing the information theoretic bound with fusion trees. J. Comput. Syst. Sci. 47(3), 424–436 (1993) CrossRefMATHMathSciNet

14.

Fredman, M.L., Willard, D.E.: Trans-dichotomous algorithms for minimum spanning trees and shortest paths. J. Comput. Syst. Sci. 48(3), 533–551 (1994) CrossRefMATHMathSciNet

15.

Karlin, A.R., Manasse, M.S., Rudolph, L., Sleator, D.D.: Competitive snoopy caching. Algorithmica 3, 77–119 (1988) CrossRefMathSciNet

16.

Koutsoupias, E., Papadimitriou, C.H.: Beyond competitive analysis. In: Proc. 35th Symposium on Foundations of Computer Science, pp. 394–400. IEEE Comput. Soc., Los Alamitos (1994) CrossRef

17.

McCreight, E.M.: Priority search trees. SIAM J. Comput. 14(2), 257–276 (1985) CrossRefMATHMathSciNet

18.

McGeoch, L.A., Sleator, D.D.: A strongly competitive randomized paging algorithm. Algorithmica 6(6), 816–825 (1991) CrossRefMATHMathSciNet

19.

Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Commun. ACM 28(2), 202–208 (1985) CrossRefMathSciNet

20.

Willard, D.E.: Examining computational geometry, van Emde Boas trees, and hashing from the perspective of the fusion tree. SIAM J. Comput. 29(3), 1030–1049 (2000) CrossRefMATHMathSciNet

Titel: OnlineMin: A Fast Strongly Competitive Randomized Paging Algorithm
verfasst von: Gerth Stølting Brodal
Gabriel Moruz
Andrei Negoescu
Publikationsdatum: 01.01.2015
Verlag: Springer US
Erschienen in: Theory of Computing Systems / Ausgabe 1/2015
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-012-9427-y

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 1/2015

Online Results for Black and White Bin Packing

Approximation Algorithms for Fragmenting a Graph Against a Stochastically-Located Threat

On Minimum- and Maximum-Weight Minimum Spanning Trees with Neighborhoods

Some Anomalies of Farsighted Strategic Behavior

Approximating Spanning Trees with Few Branches

On Online Algorithms with Advice for the k-Server Problem