The DOI matches its Crossref record; 57 of the 57 references it cites were found in a registry or an index.
Online algorithms: a survey
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Hypertext Transfer Protocol (HTTP)
(2003) · The Hacker's Handbook · doi:10.1201/9780203490044-20 · Cited by 2,824
Online Computation and Competitive Analysis
Borodin, A., & El‐Yaniv, R. (1998) · Cited by 2,333
A Block-sorting Lossless Data Compression Algorithm
Burrows, M. T., & Wheeler, D. J. (1994) · Cited by 2,333
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
A study of replacement algorithms for a virtual-storage computer
Belady, L. A. (1966) · IBM Systems Journal · doi:10.1147/sj.52.0078 · Cited by 1,659
Self-adjusting binary search trees
Sleator, D. D., & Tarjan, R. E. (1985) · Journal of the ACM · doi:10.1145/3828.3835 · Cited by 1,228
Approximation algorithms for bin packing: a survey
Coffman, E. G., Garey, M. R., & Johnson, D. S. (1996) · PWS Publishing Co. eBooks · Cited by 862
The working set model for program behavior
Denning, P. J. (1983) · Communications of the ACM · doi:10.1145/357980.357997 · Cited by 845
Speed is as powerful as clairvoyance
Kalyanasundaram, B., & Pruhs, K. (2000) · Journal of the ACM · doi:10.1145/347476.347479 · Cited by 561
A locally adaptive data compression scheme
Bentley, J. L., Sleator, D. D., Tarjan, R. E., & Wei, V. K. (1986) · Communications of the ACM · doi:10.1145/5684.5688 · Cited by 523
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
Denning, P. J. (1980) · IEEE Transactions on Software Engineering · doi:10.1109/tse.1980.230464 · Cited by 396
(1998) · Lecture Notes in Computer Science · doi:10.1007/bfb0029561 · Cited by 361
Competitive algorithms for on-line problems
Manasse, M., McGeoch, L., & Sleator, D. (1988) · Proceedings of the twentieth annual ACM symposium on Theory of computing - STOC '88 · doi:10.1145/62212.62243 · Cited by 358
Koutsoupias, E., & Papadimitriou, C. H. (2000) · SIAM Journal on Computing · doi:10.1137/s0097539796299540 · Cited by 277
On the power of randomization in on-line algorithms
Ben-David, S., Borodin, A., Karp, R., Tardos, G., & Wigderson, A. (1994) · Algorithmica · doi:10.1007/bf01294260 · Cited by 262
Competitive auctions and digital goods
Goldberg, A. V., Hartline, J. D., & Wright, A. (2001) · doi:10.5555/365411.365768 · Cited by 257
Thek-server dual and loose competitiveness for paging
Young, N. (1994) · Algorithmica · doi:10.1007/bf01189992 · Cited by 252
Sgall, J. (1998) · Lecture notes in computer science · doi:10.1007/bfb0029570 · Cited by 244
The Competitiveness of On-Line Assignments
Azar, Y., Naor, J. S., & Rom, R. (1995) · Journal of Algorithms · doi:10.1006/jagm.1995.1008 · Cited by 241
Koutsoupias, E., & Papadimitriou, C. H. (1995) · Journal of the ACM · doi:10.1145/210118.210128 · Cited by 240
Better Bounds for Online Scheduling
Albers, S. (1999) · SIAM Journal on Computing · doi:10.1137/s0097539797324874 · Cited by 239
Self-citationA strongly competitive randomized paging algorithm
McGeoch, L. A., & Sleator, D. D. (1991) · Algorithmica · doi:10.1007/bf01759073 · Cited by 238
On-line load balancing with applications to machine scheduling and virtual circuit routing
Aspnes, J., Azar, Y., Fiat, A., Plotkin, S., & Waarts, O. (1993) · Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 · doi:10.1145/167088.167248 · Cited by 212
New algorithms for an ancient scheduling problem
Bartal, Y., Fiat, A., Karloff, H. J., & Vohra, R. (1992) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/129712.129718 · Cited by 210
On-line packing and covering problems
Csirik, J., & Woeginger, G. J. (1998) · Lecture notes in computer science · doi:10.1007/bfb0029568 · Cited by 181
Competitive Paging with Locality of Reference
Borodin, A., Irani, S., Raghavan, P., & Schieber, B. (1995) · Journal of Computer and System Sciences · doi:10.1006/jcss.1995.1021 · Cited by 165
An optimal online algorithm for metrical task systems
Borodin, A., Linial, N., & Saks, M. (1987) · Proceedings of the nineteenth annual ACM conference on Theory of computing - STOC '87 · doi:10.1145/28395.28435 · Cited by 164
Dynamic TCP acknowledgement and other stories about e/(e-1)
Karlin, A. R., Mathieu, C., & Randall, D. (2001) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/380752.380845 · Cited by 155
Competitive generalized auctions
Fiat, A., Goldberg, A. V., Hartline, J. D., & Karlin, A. R. (2002) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/509907.509921 · Cited by 154
A new measure for the study of on-line algorithms
Ben-David, S., & Borodin, A. (1994) · Algorithmica · doi:10.1007/bf01294264 · Cited by 141
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
Strongly Competitive Algorithms for Paging with Locality of Reference
Irani, S., Karlin, A. R., & Phillips, S. (1996) · SIAM Journal on Computing · doi:10.1137/s0097539792236353 · Cited by 121
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
On-Line Load Balancing for Related Machines
Berman, P., Charikar, M., & Karpiński, M. (2000) · Journal of Algorithms · doi:10.1006/jagm.1999.1070 · Cited by 96
Randomized competitive algorithms for the list update problem
Reingold, N., Westbrook, J., & Sleator, D. D. (1994) · Algorithmica · doi:10.1007/bf01294261 · Cited by 96
A guessing game and randomized online algorithms
Seiden, S. S. (2000) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/335305.335385 · Cited by 91
Random walks on weighted graphs and applications to on-line algorithms
Coppersmith, D., Doyle, P. G., Raghavan, P., & Snir, M. (1993) · Journal of the ACM · doi:10.1145/174130.174131 · Cited by 90
A polylog( n )-competitive algorithm for metrical task systems
Bartal, Y., Blum, A. L., Burch, C., & Tomkins, A. (1997) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/258533.258667 · Cited by 90
On-line analysis of the TCP acknowledgment delay problem
Dooly, D. R., Goldman, S. A., & Scott, S. (2001) · Journal of the ACM · doi:10.1145/375827.375843 · Cited by 81
On-Line Load Balancing of Temporary Tasks
Azar, Y., Kalyanasundaram, B., Plotkin, S. A., et al. (1997) · Journal of Algorithms · doi:10.1006/jagm.1995.0799 · Cited by 76
A Unified Analysis of Paging and Caching
Torng, E. K. (1998) · Algorithmica · doi:10.1007/pl00009192 · Cited by 65
The Accommodating Function: A Generalization of the Competitive Ratio
Boyar, J., Larsen, K. S., & Nielsen, M. N. (2001) · SIAM Journal on Computing · doi:10.1137/s0097539799361786 · Cited by 65
The harmonic online K -server algorithm is competitive
Grove, E. F. (1991) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/103418.103448 · Cited by 62
A statistical adversary for on-line algorithms
Raghavan, P. (1992) · DIMACS series in discrete mathematics and theoretical computer science · doi:10.1090/dimacs/007/05 · Cited by 58
Karlin, A. R., Phillips, S. J., & Raghavan, P. (2000) · SIAM Journal on Computing · doi:10.1137/s0097539794268042 · Cited by 57
Randomized and multipointer paging with locality of reference
Fiat, A., & Karlin, A. R. (1995) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/225058.225280 · Cited by 53
Page Replacement with Multi-Size Pages and Applications to Web Caching
Irani, S. (2002) · Algorithmica · doi:10.1007/s00453-001-0125-4 · Cited by 49
Bartal, Y., Bollobás, B., & Mendel, M. (2001) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2001.959914 · Cited by 48
Truly online paging with locality of reference
Fiat, A., & Mendel, M. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1997.646121 · Cited by 33
Randomized algorithms for metrical task systems
Irani, S., & Seiden, S. (1998) · Theoretical Computer Science · doi:10.1016/s0304-3975(97)00006-6 · Cited by 29
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
Online Randomized Multiprocessor Scheduling
Seiden, S. S. (2000) · Algorithmica · doi:10.1007/s004530010014 · Cited by 20
On paging with locality of reference
Albers, S., Favrholdt, L. M., & Giel, O. (2002) · doi:10.1145/509907.509949 · Cited by 17
Self-citationA General Decomposition Theorem for the k-Server Problem
Seiden, S. S. (2001) · Lecture notes in computer science · doi:10.1007/3-540-44676-1_7 · Cited by 15
Cohen, E., Kaplan, H. Y., & Zwick, U. (1999) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/301250.301416 · Cited by 14
On Generalized Connection Caching
Albers, S. (2002) · Theory of Computing Systems · doi:10.1007/s00224-002-1053-7 · Cited by 8
Self-citation
Cited by
Online learning: A comprehensive survey
Hoi, S. C. H., Sahoo, D., Lu, J., & Zhao, P. (2021) · Neurocomputing · doi:10.1016/j.neucom.2021.04.112 · Cited by 746
A survey on metaheuristics for stochastic combinatorial optimization
Bianchi, L., Dorigo, M., Gambardella, L. M., & Gutjahr, W. J. (2009) · Natural Computing · doi:10.1007/s11047-008-9098-4 · Cited by 737
Home energy management systems: A review of modelling and complexity
Beaudin, M., & Zareipour, H. (2015) · Renewable and Sustainable Energy Reviews · doi:10.1016/j.rser.2015.01.046 · Cited by 471
A unified framework for stochastic optimization
Powell, W. B. (2019) · European Journal of Operational Research · doi:10.1016/j.ejor.2018.07.014 · Cited by 314
Home Energy Management Systems: A Review of Modelling and Complexity
Beaudin, M., & Zareipour, H. (2017) · Lecture Notes in Energy · doi:10.1007/978-3-319-26950-4_35 · Cited by 254
Metadata
- Authors
- Albers, S.
- Venue
- Mathematical Programming
- Published
- 2003-07
- Volume
- 97
- Issue
- 1
- Pages
- 3-26
- ISSN
- 0025-5610 (ISSN-L)
- 1436-4646
- OpenAlex
- W158123262
- Cited by
- 259
- References
- 57
- FWCI
- 4.36
- Type
- journal article
- Language
- en
- Open access
- closed
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
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.