A strongly competitive randomized paging algorithm

McGeoch, Lyle A., Sleator, Daniel D.·1991·Algorithmica
DOI 10.1007/bf01759073

Cited by (233)

Items 101–200 of 233

  1. Online algorithms for prefetching and caching on parallel disks
    Rahul Shah, Peter Varman, Jeffrey Scott Vitter · 2004 · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)
  2. A unified analysis of paging and caching
    Eric K. Torng · 2002 · Annual Symposium on Foundations of Computer Science
  3. A General Decomposition Theorem for the k-Server Problem
    Steven S. Seiden · 2001 · Lecture notes in computer science
  4. Competitive caching of query results in search engines
    Ronny Lempel, Shlomo Moran · 2004 · Theoretical Computer Science
  5. Distributed paging
    Yair Bartal · 1998 · Lecture notes in computer science
  6. Migrating and replicating data in networks
    Marcin Bieńkowski · 2011 · Computer Science - Research and Development
  7. Dynamic Balanced Graph Partitioning
    Chen Avin, Marcin Bieńkowski, Andreas Loukas, Maciej Pacut, Stefan Schmid · 2020 · SIAM Journal on Discrete Mathematics
  8. On-line Restricted Caching
    Mark Brehob, Richard J. Enbody, Eric K. Torng, Stephen Wagner · 2003 · Journal of Scheduling
  9. Connection caching
    Edith Cohen, Haim Y. Kaplan, Uri Zwick · 1999 · ACM Symposium on Theory of Computing (STOC)
  10. Competitive algorithms for multilevel caching and relaxed list update
    Marek Chrobák, John Noga · 1998 · Symposium on Discrete Algorithms
  11. Increased axonal transport of trigeminal ganglion proteins in an electrode model.
    K Y Chan, T W Beck, P Mullen, W K Dong · 1989 · PubMed
  12. Caching in networks (extended abstract)
    Friedhelm Meyer auf der Heide, Berthold Vöcking, Matthias Westermann · 2000 · Symposium on Discrete Algorithms
  13. Trackless online algorithms for the server problem
    Wolfgang W. Bein, Lawrence L. Larmore · 2000 · Information Processing Letters
  14. On Competitive On-Line Paging with Lookahead
    Dany Breslauer · 1995 · BRICS Report Series
  15. Online Optimization: Probabilistic Analysis and Algorithm Engineering
    Benjamin Hiller · 2011 · Operations research proceedings
  16. On competitive on-line paging with lookahead
    Dany Breslauer · 1996 · Lecture notes in computer science
  17. On broadcast disk paging
    Sanjeev Khanna, Vincenzo Liberatore · 1998 · ACM Symposium on Theory of Computing (STOC)
  18. Online Dynamic B-Matching
    Marcin Bieńkowski, David Fuchssteiner, Jan Marcinkowski, Stefan Schmid · 2021 · ACM SIGMETRICS Performance Evaluation Review
  19. A Randomized Algorithm for Two Servers on the Line (Extended Abstract)
    Yair Bartal, Marek Chrobák, Lawrence L. Larmore · 1998 · Lecture notes in computer science
  20. SIGACT news online algorithms column 13
    Marek Chrobák · 2008 · ACM SIGACT News
  21. Randomized On-line Scheduling of Parallel Jobs
    Jiřı́ Sgall · 1996 · Journal of Algorithms
  22. Optimal prediction for prefetching in the worst case
    P. Krishnan, Jeffrey Scott Vitter · 1994
  23. A General Decomposition Theorem for the k-Server Problem
    Steven S. Seiden · 2002 · Information and Computation
  24. A randomized on–line algorithm for thek–server problem on a line
    Béla Csaba, Sachin Lodha · 2006 · Random Structures and Algorithms
  25. More on randomized on-line algorithms for caching
    Marek Chrobák, Elias Koutsoupias, John Noga · 2003 · Theoretical Computer Science
  26. Online Algorithms
    Susanne Albers · 2006 · Springer eBooks
  27. Um algoritmo enumerativo baseado em ordenamento parcial para resolução do problema de minimização de trocas de ferramentas
    Horácio Hideki Yanasse, Rita de Cássia Meneses Rodrigues, Edson Luiz França Senne · 2009 · Gestão & Produção
  28. Connection caching under various models of communication
    Edith Cohen, Haim Y. Kaplan, Uri Zwick · 2000 · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)
  29. The Weighted 2-Server Problem
    Marek Chrobák, Jiřı́ Sgall · 2000 · Lecture notes in computer science
  30. On-Line Algorithms and the k-Server Conjecture
    Elias Koutsoupias · 1994
  31. Probabilistic alternatives for competitive analysis
    Benjamin Hiller, Tjark Vredeveld · 2011 · Computer Science - Research and Development
  32. Competitive Clustering of Stochastic Communication Patterns on a Ring
    Chen Avin, Louis Cohen, Stefan Schmid · 2017 · Lecture notes in computer science
  33. Concurrency-Informed Orchestration for Serverless Functions
    Qichang Liu, Yue Cheng, Haiying Shen, Ao Wang, Bharathan Balaji · 2025 · International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS)
  34. Optimal Online Balanced Graph Partitioning
    Maciej Pacut, Mahmoud Parham, Stefan Schmid · 2021 · IEEE Conference on Computer Communications (INFOCOM)
  35. Energy Efficient Caching for Phase-Change Memory
    Neal Barcelo, Miao Zhou, Daniel G. Cole, Michael Nugent, Kirk R. Pruhs · 2012 · Lecture notes in computer science
  36. Competitive clustering of stochastic communication patterns on a ring
    Chen Avin, Louis Cohen, Mahmoud Parham, Stefan Schmid · 2018 · Computing
  37. Lower Bounds for Caching with Delayed Hits
    Peter Manohar, Jalani Williams · 2020 · arXiv (Cornell University)
  38. OnlineMin: A Fast Strongly Competitive Randomized Paging Algorithm
    Gerth Stølting Brodal, Gabriel Moruz, Andrei Negoescu · 2012 · Theory of Computing Systems
  39. Exploiting symmetry for the job sequencing and tool switching problem
    Najmaddin Akhundov, James Ostrowski · 2024 · European Journal of Operational Research
  40. A proof of the optimality of the MIN paging algorithm using linear programming duality
    Ariel C. Cohen, Walter A. Burkhard · 1995 · Operations Research Letters
  41. Connection caching: model and algorithms
    Edith Cohen, Haim Y. Kaplan, Uri Zwick · 2003 · Journal of Computer and System Sciences
  42. Exploiting Reuse in Pipeline-Aware Hyperparameter Tuning
    Liam Li, Evan Sparks, Kevin Jamieson, Ameet Talwalkar · 2019 · arXiv (Cornell University)
  43. General Caching Is Hard: Even with Small Pages
    Lukáš Folwarczný, Jiřı́ Sgall · 2015 · Lecture notes in computer science
  44. Randomized algorithm for the k-server problem on decomposable spaces
    Judit Nagy-György · 2009 · Journal of Discrete Algorithms
  45. Equitable Revisited
    Wolfgang W. Bein, Lawrence L. Larmore, John Noga · 2007 · Springer eBooks
  46. New Results on Web Caching with Request Reordering
    Susanne Albers · 2009 · Algorithmica
  47. Competitive Algorithms for Relaxed List Update and Multilevel Caching
    Marek Chrobák, John Noga · 2000 · Journal of Algorithms
  48. Online Companion Caching
    Amos Fiat, Manor Mendel, Steven S. Seiden · 2002 · Lecture notes in computer science
  49. Online Paging and Caching
    Neal E. Young · 2016 · Encyclopedia of Algorithms
  50. Randomized parallel prefetching and buffer management
    Peter Varman · 1998 · Lecture notes in computer science
  51. Stochastic k-Server: How Should Uber Work?
    Sina Dehghani, Soheil Ehsani, MohammadTaghi Hajiaghayi, Vahid Liaghat, Saeed Seddighin · 2017 · arXiv (Cornell University)
  52. Online Paging and Caching
    Neal E. Young · 2008 · Encyclopedia of Algorithms
  53. Competitive Algorithms for Generalized k -Server in Uniform Metrics
    Nikhil Bansal, Marek Eliáš, Grigorios Koumoutsos, Jesper Nederlof · 2022 · ACM Transactions on Algorithms
  54. Efficient Online Weighted Multi-Level Paging
    Nikhil Bansal, Joseph Seffi Naor, Ohad Talmon · 2021 · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)
  55. Randomized online multi-threaded paging
    Steven S. Seiden · 1998 · Lecture notes in computer science
  56. Application-controlled paging for a shared cache
    Rakesh D. Barve, E.F. Grove, Jeffrey Scott Vitter · 2002 · Annual Symposium on Foundations of Computer Science
  57. Dependency-Aware Online Caching
    Julien Dallot, Amirmehdi Jafari Fesharaki, Maciej Pacut, Stefan Schmid · 2024 · IEEE Conference on Computer Communications (INFOCOM)
  58. On the Smoothness of Paging Algorithms
    Jan Reineke, Alejandro Salinger · 2015 · Lecture notes in computer science
  59. OnlineMin: A Fast Strongly Competitive Randomized Paging Algorithm
    Gerth Stølting Brodal, Gabriel Moruz, Andrei Negoescu · 2012 · Lecture notes in computer science
  60. Memoryless Algorithms for the Generalized k-server Problem on Uniform Metrics
    Dimitris Christou, Dimitris A. Fotakis, Grigorios Koumoutsos · 2021 · Lecture notes in computer science
  61. Online paging with arbitrary associativity
    Enoch Peserico · 2003 · Symposium on Discrete Algorithms
  62. On-line restricted caching
    Mark Brehob, Richard J. Enbody, Eric K. Torng, Stephen Wagner · 2001 · Symposium on Discrete Algorithms
  63. The Worst Page-Replacement Policy
    Kunal Agrawal, Michael A. Bender, Jeremy T. Fineman · 2008 · Theory of Computing Systems
  64. Generalized Reordering Buffer Management
    Yossi Azar, Matthias Englert, Iftah Gamzu, Eytan Kidron · 2014 · Warwick Research Archive Portal (University of Warwick)
  65. Page Migration in Dynamic Networks
    Marcin Bieńkowski, Friedhelm Meyer auf der Heide · 2005 · Lecture notes in computer science
  66. Online Occlusion Culling
    Gereon Frahling, Jens Krokowski · 2005 · Lecture notes in computer science
  67. Competitive Algorithms for Block-Aware Caching
    Christian Coester, Roie Levin, Joseph Seffi Naor, Ohad Talmon · 2022 · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)
  68. Online Paging with Heterogeneous Cache Slots
    Marek Chrobák, Samuel Haney, Mehraneh Liaee, Debmalya Panigrahi, Rajmohan Rajaraman, Ravi Sundaram, Neal E. Young · 2024 · Algorithmica
  69. Online View Maintenance Under a Response-Time Constraint
    Kamesh Munagala, Jun Yang, Hai Yu · 2005 · Lecture notes in computer science
  70. On Variants of File Caching
    Leah Epstein, Csanád Imreh, Asaf Levin, Judit Nagy-György · 2011 · Lecture notes in computer science
  71. Uniform multipaging reduces to paging
    Vincenzo Liberatore · 1998 · Information Processing Letters
  72. Unbounded lower bound for k-server against weak adversaries
    Marcin Bieńkowski, Jarosław Byrka, Christian Coester, Łukasz Jeż · 2020 · ACM Symposium on Theory of Computing (STOC)
  73. Paging more than one page
    Esteban Feuerstein · 1997 · Theoretical Computer Science
  74. Optimizing Reconfigurable Optical Datacenters: The Power of Randomization
    Marcin Bieńkowski, David Fuchssteiner, Stefan Schmid · 2023 · International Conference for High Performance Computing, Networking, Storage and Analysis (SC)
  75. Engineering Efficient Paging Algorithms
    Gabriel Moruz, Andrei Negoescu, Christian Neumann, Volker Weichert · 2015 · ACM Journal of Experimental Algorithmics
  76. The working set algorithm has competitive ratio less than two
    Kunsoo Park, Sang Lyul Min, Yookun Cho · 1997 · Information Processing Letters
  77. Distributed Multi-Depot Routing without Communications
    Dawsen Hwang, Patrick Jaillet, Zhengyuan Zhou · 2014 · arXiv (Cornell University)
  78. Paging with connections: FIFO strikes again
    Leah Epstein, Yanir Kleiman, Jiřı́ Sgall, Rob van Stee · 2007 · Theoretical Computer Science
  79. Caching with rental cost and zapping
    Khare, Monik, Young, Neal E. · 2012 · arXiv
  80. Online Paging for Flash Memory Devices
    Annamária Kovács, Ulrich Meyer, Gabriel Moruz, Andrei Negoescu · 2009 · Lecture notes in computer science
  81. The k -resource problem in uniform metric spaces
    Marcin Bieńkowski, Jarosław Kutyłowski · 2012 · Theoretical Computer Science
  82. Paging with Request Sets
    Leah Epstein, Rob van Stee, Tami Tamir · 2007 · Theory of Computing Systems
  83. On the Smoothness of Paging Algorithms
    Jan Reineke, Alejandro Salinger · 2017 · Theory of Computing Systems
  84. Object Caching for Queries and Updates
    Philip Little, Amitabh Chaudhary · 2009 · Lecture notes in computer science
  85. Can competitive analysis be made competitive
    Allan Borodin · 1992 · Conference of the Centre for Advanced Studies on Collaborative Research
  86. The Worst Page-Replacement Policy
    Kunal Agrawal, Michael A. Bender, Jeremy T. Fineman · 2007 · Lecture notes in computer science
  87. Optimal Online Algorithms for File-Bundle Caching and Generalization to Distributed Caching
    Tiancheng Qin, S. Rasoul Etesami · 2021 · ACM Transactions on Modeling and Performance Evaluation of Computing Systems
  88. A Platform for Scalable Low-Latency Analytics using MapReduce
    Boduo Li · 2021 · Scholarworks (University of Massachusetts Amherst)
  89. A Study of Integrated Document and Connection Caching
    Susanne Albers, Rob van Stee · 2003 · Lecture notes in computer science
  90. Paging
    Rob van Stee · 2008 · Encyclopedia of Algorithms
  91. Production Planning
    Nadia Brauner, Gerd Finke, Maurice Queyranne · 2014 · Wiley eBooks
  92. Adversarial models in paging
    Alexander Souza · 2011 · Computer Science - Research and Development
  93. Learning-Augmented Weighted Paging
    Nikhil Bansal, Christian Coester, Ravi Kumar, Manish Purohit, Erik Vee · 2022 · Society for Industrial and Applied Mathematics eBooks
  94. The optimal structure of algorithms for α -paging
    Annamária Kovács, Ulrich Meyer, Gabriel Moruz, Andrei Negoescu · 2015 · Information Processing Letters
  95. Paging with Request Sets
    Leah Epstein, Rob van Stee, Tami Tamir · 2006 · Lecture notes in computer science
  96. Improved Space Bounds for Strongly Competitive Randomized Paging Algorithms
    Gabriel Moruz, Andrei Negoescu · 2013 · Lecture notes in computer science
  97. A New Competitive Analysis of Randomized Caching
    Ching Law, Charles E. Leiserson · 2000 · Lecture notes in computer science
  98. Online algorithms for combinatorial problems
    Judit Nagy-György · 2009 · SZTE Repository of Dissertations (University of Szeged)
  99. Paging on a RAM with Limited Resources
    Tony W. Lai · 2002 · Lecture notes in computer science
  100. MOO: A Methodology for Online Optimization through Mining the Offline Optimum
    Jason W. H. Lee, Yong Chiang Tay, Anthony K. H. Tung · 2000 · arXiv (Cornell University)