A strongly competitive randomized paging algorithm
Open accessIntegrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The (e/(e-1))-competitive randomized online algorithm for ski-rental [12] and the H_k-competitive randomized online algorithm for caching [1, 16], give a (H_k + e/(e-1))-competitive randomized online algorithm for rental caching.
“Corollary 3.7. The ( e e -1 ) -competitive randomized online algorithm for ski-rental [12] and the H k -competitive randomized online algorithm for caching [1, 16], give a ( H k + e e -1 ) -competitive randomized online algorithm for rental caching.”
From Caching with rental cost and zapping (2012) · cites this paper as [16]
Cites
Amortized efficiency of list update and paging rules
Sleator, D. D., & Tarjan, R. E. (1985) · Communications of the ACM · doi:10.1145/2786.2793 · Cited by 2,123 · see citing works
Self-citationA Study of Replacement Algorithms for Virtual-Storage Computer
Belady, L. (1966) · IBM Systems Journal · doi:10.1147/sj.52.0078 · Cited by 1,947 · see citing works
Fiat, A., Karp, R. M., Luby, M., McGeoch, L. A., Sleator, D. D., & Young, N. E. (1991) · Journal of Algorithms · doi:10.1016/0196-6774(91)90041-v · Cited by 457 · see citing works
Self-citationCompetitive algorithms for server problems
Manasse, M. S., McGeoch, L. A., & Sleator, D. D. (1990) · Journal of Algorithms · doi:10.1016/0196-6774(90)90003-w · Cited by 423 · see citing works
Self-citationCompetitive algorithms for on-line problems
Manasse, M. S., McGeoch, L. A., & Sleator, D. D. (1988) · doi:10.1145/62212.62243 · Cited by 359 · see citing works
Self-citation
Flagged first, then by citations
1 of the 6 references couldn’t be matched to a known paper.
Cited by
Sorted by citations
Fiat, A., Karp, R. M., Luby, M., McGeoch, L. A., Sleator, D. D., & Young, N. E. (1991) · Journal of Algorithms · doi:10.1016/0196-6774(91)90041-v · Cited by 457 · see citing works
Self-citationCompetitive algorithms for server problems
Manasse, M. S., McGeoch, L. A., & Sleator, D. D. (1990) · Journal of Algorithms · doi:10.1016/0196-6774(90)90003-w · Cited by 423 · see citing works
Self-citationAn optimal on-line algorithm for metrical task system
Borodin, A., Linial, N., & Saks, M. (1992) · Journal of the ACM · doi:10.1145/146585.146588 · Cited by 331 · see citing works
Koutsoupias, E., & Papadimitriou, C. H. (2000) · SIAM Journal on Computing · doi:10.1137/s0097539796299540 · Cited by 274 · see citing works
The Design of Competitive Online Algorithms via a Primal—Dual Approach
Buchbinder, N., & Naor, J. S. (2009) · now publishers, Inc. eBooks · doi:10.1561/9781601982179 · Cited by 266 · see citing works
On the power of randomization in on-line algorithms
Ben-David, S., Borodin, A., Karp, R. M., Tardos, G., & Wigderson, A. (1994) · Algorithmica · doi:10.1007/bf01294260 · Cited by 263 · see citing works
Competitive randomized algorithms for nonuniform problems
Karlin, A. R., Manasse, M. S., McGeoch, L. A., & Owicki, S. (1994) · Algorithmica · doi:10.1007/bf01189993 · Cited by 258 · see citing works
Self-citationAlbers, S. (2003) · Mathematical Programming · doi:10.1007/s10107-003-0436-0 · Cited by 255 · see citing works
Thek-server dual and loose competitiveness for paging
Young, N. E. (1994) · Algorithmica · doi:10.1007/bf01189992 · Cited by 252 · see citing works
Pedarsani, R., Maddah-Ali, M. A., & Niesen, U. (2015) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2015.2394482 · Cited by 236 · see citing works
The Design of Competitive Online Algorithms via a Primal—Dual Approach
Buchbinder, N., & Naor, J. S. (2009) · Foundations and Trends® in Theoretical Computer Science · doi:10.1561/0400000024 · Cited by 222 · see citing works
New Ressults on Server Problems
Chrobák, M., Karloof, H., Payne, T., & Vishwnathan, S. (1991) · SIAM Journal on Discrete Mathematics · doi:10.1137/0404017 · Cited by 211 · see citing works
On the power of randomization in online algorithms
Ben-David, S., Borodin, A., Karp, R. M., Tardos, G., & Wigderson, A. (1990) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/100216.100268 · Cited by 176 · see citing works
An Optimal On-Line Algorithm for K Servers on Trees
Chrobák, M., & Larmore, L. L. (1991) · SIAM Journal on Computing · doi:10.1137/0220008 · Cited by 161 · see citing works
Competitive randomized algorithms for non-uniform problems
Karlin, A. R., Manasse, M. S., McGeoch, L. A., & Owicki, S. S. (1990) · Symposium on Discrete Algorithms · doi:10.5555/320176.320216 · Cited by 158 · see citing works
Self-citationA new measure for the study of on-line algorithms
Ben-David, S., & Borodin, A. (1994) · Algorithmica · doi:10.1007/bf01294264 · Cited by 141 · see citing works
Optimal prefetching via data compression
Vitter, J. S., & Krishnan, P. (1996) · Journal of the ACM · doi:10.1145/234752.234753 · Cited by 137 · see citing works
Competitive k-server algorithms
Fiat, A., Rabani, Y., & Ravid, Y. (1994) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(05)80060-1 · Cited by 135 · see citing works
Competitive analysis of randomized paging algorithms
Achlioptas, D., Chrobak, M., & Noga, J. (2000) · Theoretical Computer Science · doi:10.1016/s0304-3975(98)00116-9 · Cited by 127 · see citing works
Combinatorial optimization models for production scheduling in automated manufacturing systems
Crama, Y. (1997) · European Journal of Operational Research · doi:10.1016/s0377-2217(96)00388-8 · Cited by 122 · see citing works
Memory versus randomization in on-line algorithms
Rajhavan, P., & Snir, M. (1994) · IBM Journal of Research and Development · doi:10.1147/rd.386.0683 · Cited by 118 · see citing works
On-line caching as cache size varies
Young, N. E. (1991) · Symposium on Discrete Algorithms · doi:10.5555/127787.127832 · Cited by 101 · see citing works
Haitner, I., Hoch, J. J., Reingold, O., & Segev, G. (2007) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2007.4389535 · Cited by 99 · see citing works
Near-Optimal Bounds for Online Caching with Machine Learned Advice
Rohatgi, D. (2019) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611975994.112 · Cited by 98 · see citing works
Randomized on-line scheduling on two uniform machines
Epstein, L., Noga, J., Seiden, S., Sgall, J., & Woeginger, G. J. (2001) · Journal of Scheduling · doi:10.1002/jos.60 · Cited by 97 · see citing works
Young, N. E. (1998) · doi:10.5555/314613.314658 · Cited by 88 · see citing works
The server problem and on-line games
Chrobák, M., & Larmore, L. L. (1992) · DIMACS series in discrete mathematics and theoretical computer science · doi:10.1090/dimacs/007/02 · Cited by 88 · see citing works
Competitive paging with locality of reference
Borodin, A., Raghavan, P., Irani, S., & Schieber, B. (1991) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/103418.103422 · Cited by 85 · see citing works
Young, N. E. (2002) · Algorithmica · doi:10.1007/s00453-001-0124-5 · Cited by 105 · see citing works
Exact algorithms for the job sequencing and tool switching problem
Gilbert Laporte, A., Salazar‐González, J., & Semet, F. (2004) · IIE Transactions · doi:10.1080/07408170490257871 · Cited by 75 · see citing works
A Primal-Dual Randomized Algorithm for Weighted Paging
Bansal, N., Buchbinder, N., & Naor, J. S. (2012) · Journal of the ACM · doi:10.1145/2339123.2339126 · Cited by 72 · see citing works
Pedarsani, R., Maddah-Ali, M. A., & Niesen, U. (2014) · International Conference on Communications · doi:10.1109/icc.2014.6883597 · Cited by 68 · see citing works
On the Influence of Lookahead in Competitive Paging Algorithms
Albers, S. (1997) · Algorithmica · doi:10.1007/pl00009158 · Cited by 68 · see citing works
Boyar, J., Favrholdt, L. M., Kudahl, C., Larsen, K. S., & Mikkelsen, J. W. (2017) · ACM Computing Surveys · doi:10.1145/3056461 · Cited by 66 · see citing works
k-server via multiscale entropic regularization
Bubeck, S., Cohen, M. B., Lee, Y. T., Lee, J. R., & Mądry, A. (2018) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3188745.3188798 · Cited by 66 · see citing works
A Unified Analysis of Paging and Caching
Torng, E. K. (1998) · Algorithmica · doi:10.1007/pl00009192 · Cited by 65 · see citing works
A Polylogarithmic-Competitive Algorithm for the k-Server Problem
Bansal, N., Buchbinder, N., Mądry, A., & Naor, J. S. (2011) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2011.63 · Cited by 64 · see citing works
Optimal prefetching via data compression
Vitter, J. S., & Krishnan, P. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1991.185360 · Cited by 64 · see citing works
Ramsey-type theorems for metric spaces with applications to online problems
Bartal, Y., Bollobás, B., & Mendel, M. (2006) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2005.05.008 · Cited by 63 · see citing works
Beyond competitive analysis [on-line algorithms]
Koutsoupias, E., & Papadimitriou, C. H. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365677 · Cited by 59 · see citing works
Online Competitive Algorithms for Maximizing Weighted Throughput of Unit Jobs
Bartal, Y., Chin, F. Y. L., Chrobák, M., Fung, S. P. Y., Jawor, W., Lavi, R., Sgall, J., & Tichý, T. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-24749-4_17 · Cited by 57 · see citing works
On-Line Paging Against Adversarially Biased Random Inputs
Young, N. E. (2000) · Journal of Algorithms · doi:10.1006/jagm.2000.1099 · Cited by 56 · see citing works
Online Algorithms with Advice: A Survey
Boyar, J., Favrholdt, L. M., Kudahl, C., Larsen, K. S., & Mikkelsen, J. W. (2016) · ACM SIGACT News · doi:10.1145/2993749.2993766 · Cited by 54 · see citing works
Greedy Δ-Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost
Koufogiannakis, C., & Young, N. E. (2013) · Algorithmica · doi:10.1007/s00453-012-9629-3 · Cited by 53 · see citing works
Optimal prefetching and caching for parallel I/O sytems
Kallahalla, M., & Varman, P. (2001) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/378580.378648 · Cited by 49 · see citing works
Competitive k-server algorithms
Fiat, A., Rabani, Y., & Ravid, Y. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/fscs.1990.89566 · Cited by 49 · see citing works
The relative worst-order ratio applied to paging
Boyar, J., Favrholdt, L. M., & Larsen, K. S. (2007) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2007.03.001 · Cited by 48 · see citing works
Improved heuristic algorithms for the Job Sequencing and Tool Switching Problem
Paiva, G. S., & Carvalho, M. A. M. (2017) · Computers & Operations Research · doi:10.1016/j.cor.2017.07.013 · Cited by 47 · see citing works
A Polylogarithmic-Competitive Algorithm for the k -Server Problem
Bansal, N., Buchbinder, N., Mądry, A., & Naor, J. S. (2015) · Journal of the ACM · doi:10.1145/2783434 · Cited by 46 · see citing works
Rethinking Belady's Algorithm to Accommodate Prefetching
Jain, A., & Lin, C. (2018) · Proceedings - International Symposium on Computer Architecture/Proceedings · doi:10.1109/isca.2018.00020 · Cited by 44 · see citing works
Modelling a tool switching problem on a single NC-machine
Privault, C., & Finke, G. (1995) · Journal of Intelligent Manufacturing · doi:10.1007/bf00123680 · Cited by 44 · see citing works
Farach-Colton, M., & Liberatore, V. (1998) · doi:10.5555/314613.314848 · Cited by 43 · see citing works
Improved integer linear programming formulations for the job Sequencing and tool Switching Problem
Catanzaro, D., Gouveia, L., & Labbé, M. (2015) · European Journal of Operational Research · doi:10.1016/j.ejor.2015.02.018 · Cited by 42 · see citing works
A decomposition theorem and bounds for randomized server problems
Blum, A. L., Karloff, H. J., Rabani, Y., & Saks, M. (1992) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1992.267772 · Cited by 42 · see citing works
Randomized competitive algorithms for generalized caching
Bansal, N., Buchbinder, N., & Naor, J. S. (2008) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1374376.1374412 · Cited by 41 · see citing works
Competitive algorithms for the weighted server problem
Fiat, A., & Ricklin, M. (1994) · Theoretical Computer Science · doi:10.1016/0304-3975(94)90154-6 · Cited by 38 · see citing works
Optimal Prediction for Prefetching in the Worst Case
Krishnan, P., & Vitter, J. S. (1998) · SIAM Journal on Computing · doi:10.1137/s0097539794261817 · Cited by 36 · see citing works
An O (log k )-Competitive Algorithm for Generalized Caching
Adamaszek, A., Czumaj, A., Englert, M., & Räcke, H. (2018) · ACM Transactions on Algorithms · doi:10.1145/3280826 · Cited by 35 · see citing works
Scheduling with resource management in manufacturing systems
Błażewicz, J., & Finke, G. (1994) · European Journal of Operational Research · doi:10.1016/0377-2217(94)90002-7 · Cited by 35 · see citing works
Fusible HSTs and the Randomized k-Server Conjecture
Lee, J. R. (2018) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2018.00049 · Cited by 33 · see citing works
Azar, Y., Ganesh, A., Ge, R., & Panigrahi, D. (2017) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3055399.3055475 · Cited by 33 · see citing works
Randomized Competitive Algorithms for Generalized Caching
Bansal, N., Buchbinder, N., & Naor, J. S. (2012) · SIAM Journal on Computing · doi:10.1137/090779000 · Cited by 32 · see citing works
Li, B., Mazur, E., Diao, Y., McGregor, A., & Shenoy, P. J. (2012) · ACM Transactions on Database Systems · doi:10.1145/2389241.2389246 · Cited by 30 · see citing works
A Primal-Dual Randomized Algorithm for Weighted Paging
Bansal, N., Buchbinder, N., & Naor, J. S. (2007) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2007.43 · Cited by 29 · see citing works
Lower Bounds for Randomized k -Server and Motion-Planning Algorithms
Karloff, H. J., Rabani, Y., & Ravid, Y. (1994) · SIAM Journal on Computing · doi:10.1137/s0097539792224838 · Cited by 29 · see citing works
Competitive analysis of paging
Irani, S. (1998) · Lecture notes in computer science · doi:10.1007/bfb0029564 · Cited by 29 · see citing works
Competitive analysis of randomized paging algorithms
Achlioptas, D., Chrobák, M., & Noga, J. (1996) · Lecture notes in computer science · doi:10.1007/3-540-61680-2_72 · Cited by 29 · see citing works
Online File Caching with Rejection Penalties
Epstein, L., Imreh, C., Levin, A., & Nagy-György, J. (2013) · Algorithmica · doi:10.1007/s00453-013-9793-0 · Cited by 28 · see citing works
On competitive on-line paging with lookahead
Breslauer, D. (1998) · Theoretical Computer Science · doi:10.1016/s0304-3975(98)00118-2 · Cited by 28 · see citing works
PC-OPT: optimal offline prefetching and caching for parallel I/O systems
Kallahalla, M., & Varman, P. (2002) · IEEE Transactions on Computers · doi:10.1109/tc.2002.1047757 · Cited by 28 · see citing works
Farach-Colton, M., & Liberatore, V. (2000) · Journal of Algorithms · doi:10.1006/jagm.2000.1095 · Cited by 28 · see citing works
Online Balanced Repartitioning
Avin, C., Loukas, A., Pacut, M., & Schmid, S. (2016) · Lecture notes in computer science · doi:10.1007/978-3-662-53426-7_18 · Cited by 27 · see citing works
A better lower bound on the competitive ratio of the randomized 2-server problem
Chrobák, M., Larmore, L. L., Lund, C., & Reingold, N. (1997) · Information Processing Letters · doi:10.1016/s0020-0190(97)00099-9 · Cited by 27 · see citing works
A Decomposition Theorem for Task Systems and Bounds for Randomized Server Problems
Blum, A. L., Karloff, H. J., Rabani, Y., & Saks, M. (2000) · SIAM Journal on Computing · doi:10.1137/s0097539799351882 · Cited by 27 · see citing works
Chrobák, M., & Sgall, J. (2004) · Theoretical Computer Science · doi:10.1016/j.tcs.2004.05.020 · Cited by 25 · see citing works
Application-Controlled Paging for a Shared Cache
Barve, R. D., Grove, E. F., & Vitter, J. S. (2000) · SIAM Journal on Computing · doi:10.1137/s0097539797324278 · Cited by 24 · see citing works
Heat and Dump: competitive distributed paging
Awerbuch, B., Bartal, Y., & Fiat, A. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1993.366885 · Cited by 24 · see citing works
Scheduling multi-colour print jobs with sequence-dependent setup times
Burger, A. P., Jacobs, C. G., van Vuuren, J. H., & Visagie, S. E. (2014) · Journal of Scheduling · doi:10.1007/s10951-014-0400-2 · Cited by 23 · see citing works
Better algorithms for unfair metrical task systems and applications
Fiat, A., & Mendel, M. (2000) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/335305.335408 · Cited by 23 · see citing works
Erasing Belady's limitations: in search of flash cache offline optimality
Cheng, Y., Douglis, F., Shilane, P., Trachtman, M., Wallace, G., Desnoyers, P. J., & Li, K. (2016) · USENIX Annual Technical Conference · Cited by 22 · see citing works
The online tool switching problem with non-uniform tool size
Matzliach, B. (1998) · International Journal of Production Research · doi:10.1080/002075498192120 · Cited by 22 · see citing works
Online Algorithms for Caching Multimedia Streams
Andrews, M., & Munagala, K. (2000) · Lecture notes in computer science · doi:10.1007/3-540-45253-2_7 · Cited by 22 · see citing works
Koufogiannakis, C., & Young, N. E. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-02927-1_53 · Cited by 21 · see citing works
Randomized Weighted Caching with Two Page Weights
Irani (2002) · Algorithmica · doi:10.1007/s00453-001-0095-6 · Cited by 21 · see citing works
A Randomized Algorithm for Two Servers on the Line
Bartal, Y., Chrobák, M., & Larmore, L. L. (2000) · Information and Computation · doi:10.1006/inco.1999.2809 · Cited by 21 · see citing works
A new multicommodity flow model for the job sequencing and tool switching problem
da Silva, T. T., Chaves, A. A., & Yanasse, H. H. (2020) · International Journal of Production Research · doi:10.1080/00207543.2020.1748906 · Cited by 20 · see citing works
Competitive Cache Replacement Strategies for Shared Cache Environments
Katti, A. K., & Ramachandran, V. (2012) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2012.29 · Cited by 20 · see citing works
Khanna, S., & Liberatore, V. (2000) · SIAM Journal on Computing · doi:10.1137/s0097539798341399 · Cited by 20 · see citing works
The relative worst order ratio applied to paging
Boyar, J., Favrholdt, L. M., & Larsen, K. S. (2005) · doi:10.5555/1070432.1070534 · Cited by 20 · see citing works
Lower bounds for randomized k-server and motion-planning algorithms
Karloff, H. J., Rabani, Y., & Ravid, Y. (1991) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/103418.103450 · Cited by 19 · see citing works
An exact solution to the TLP problem in an NC machine
Ghiani, G., Grieco, A., & Guerriero, E. (2007) · Robotics and Computer-Integrated Manufacturing · doi:10.1016/j.rcim.2007.02.011 · Cited by 18 · see citing works
k-server problems with bulk requests: an application to tool switching in manufacturing
Privault, C., & Finke, G. (2000) · Annals of Operations Research · doi:10.1023/a:1018939132489 · Cited by 18 · see citing works
Randomized k-server algorithms for growth-rate bounded graphs
Bartal, Y., & Mendel, M. (2004) · Journal of Algorithms · doi:10.1016/j.jalgor.2004.06.002 · Cited by 18 · see citing works
The influence of lookahead in competitive paging algorithms
Albers, S. (1993) · Lecture notes in computer science · doi:10.1007/3-540-57273-2_39 · Cited by 18 · see citing works
Mendel, M., & Seiden, S. S. (2004) · Theoretical Computer Science · doi:10.1016/j.tcs.2004.05.015 · Cited by 17 · see citing works
New results on web caching with request reordering
Albers, S. (2004) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/1007912.1007925 · Cited by 17 · see citing works
Westermann, M. (1999) · Informatik aktuell · doi:10.1007/978-3-662-01069-3_42 · Cited by 17 · see citing works
Combining request scheduling with web caching
Feder, T., Motwani, R., Panigrahy, R., Seiden, S., van Stee, R., & Zhu, A. (2004) · Theoretical Computer Science · doi:10.1016/j.tcs.2004.05.016 · Cited by 16 · see citing works
Competitive Algorithms for Restricted Caching and Matroid Caching
Buchbinder, N., Chen, S., & Naor, J. S. (2014) · Lecture notes in computer science · doi:10.1007/978-3-662-44777-2_18 · Cited by 15 · see citing works
Bieńkowski, M., Marcinkowski, J., Pacut, M., Schmid, S., & Spyra, A. (2017) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/3087556.3087558 · Cited by 15 · see citing works
- Authors
- McGeoch, L. A., & Sleator, D. D.
- Affiliations
- Amherst College (US)
- Carnegie Mellon University (US)
- Venue
- Algorithmica
- Published
- 1991-06
- Volume
- 6
- Issue
- 1-6
- Pages
- 816-825
- ISSN
- 0178-4617 (ISSN-L)
- 1432-0541
- OpenAlex
- W2083392624
- Cited by
- 238
- References
- 6
- Citations by year
- 2026: 1 · 2025: 1 · 2024: 3 · 2023: 1 · 2022: 5 · 2021: 8 · 2020: 6 · 2019: 2 · 2018: 5 · 2017: 10 · 2016: 6 · 2015: 10 · 2014: 8 · 2013: 5 · 2012: 11
- FWCI
- 10.98
- Type
- journal article
- Language
- en
- Open access
- green
- figshare.com
- Licence
- Locations
- Algorithmica (publishedVersion)
- KiltHub Repository (submittedVersion)
- Figshare (submittedVersion, cc-by)
- KiltHub Repository
- Topics
- Physical Sciences › Computer Science › Computer Networks and Communications › Optimization and Search Problems
- Physical Sciences › Computer Science › Artificial Intelligence › Algorithms and Data Compression
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Keywords
- randomized online algorithms, partitioning algorithms, page faults, competitive ratio, harmonic numbers, memory management, lower bounds
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
