The DOI matches its Crossref record; 8 of the 8 references it cites were found in a registry or an index.
Dynamic TCP Acknowledgment and Other Stories about e/(e - 1)
Overview
Integrity signals
Registry
Cites
Statistics
Verification
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?
In the citing paper
“It has been proved that the best possible competitive ratio for the classical skirental problem against the adaptive adversary approaches to 2.”
From Competitive Analysis for Multi-Commodity Ski-Rental Problem (2022) · cites this paper as Karlin et al., 2003
In the citing paper
“Please note that if we consider all commodities in S as a whole with renting cost d = ∑ s i ∈ S d i and buying cost c = ∑ s i ∈ S c i , the problem can be modeled by the classical ski-rental problem [Karlin et al. , 2003].”
From Competitive Analysis for Multi-Commodity Ski-Rental Problem (2022) · cites this paper as Karlin et al., 2003
In the citing paper
“If we employ the classical ski-rental algorithm on each commodity, the customer will buy all commodities when he/she goes skiing for the hundredth time. Then, the competitive ratio is (9 . 9+10) × 3 10 × 3 = 1 . 99 .”
From Competitive Analysis for Multi-Commodity Ski-Rental Problem (2022) · cites this paper as Karlin et al., 2003
Citations
Cites
Online Computation and Competitive Analysis
Borodin, A., & El‐Yaniv, R. (1998) · Cited by 2,333
Karlin, A. R., Manasse, M. S., Rudolph, L., & Sleator, D. D. (1988) · Algorithmica · doi:10.1007/bf01762111 · Cited by 631 · cited 1×
“There is a natural deterministic online algorithm that achieves a competitive ratio of 2 [ 8 ], and a randomized online algorithm that achieves a competitive ratio of e/(e − 1) (which is about 1.58) in the limit as the ratio between the buy cost and the rent cost becomes large [7].”
BackgroundInfluentialBetter Bounds for Online Scheduling
Albers, S. (1999) · SIAM Journal on Computing · doi:10.1137/s0097539797324874 · Cited by 239
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
Fleischer, R. (1998) · Lecture notes in computer science · doi:10.1007/3-540-68535-9_10 · Cited by 95
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
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 78
TCP Dynamic Acknowledgment Delay: Theory and Practice
Dooly, D. R. (1998) · Open Scholarship Institutional Repository (Washington University in St. Louis) · doi:10.7936/k7db801w · Cited by 24
Cited by
Energy-efficient algorithms for flow time minimization
Albers, S., & Fujiwara, H. (2007) · ACM Transactions on Algorithms · doi:10.1145/1290672.1290686 · Cited by 215
Online Algorithms for Rent-Or-Buy with Expert Advice.
Gollapudi, S., & Panigrahi, D. (2019) · International Conference on Machine Learning · Cited by 169
Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online AlgorithmsPreprint
Wei, A., & Zhang, F. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2010.11443 · Cited by 112
Improving Online Algorithms via ML Predictions
Kumar, R., Purohit, M., & Svitkina, Z. (2024) · arXiv · doi:10.48550/arxiv.2407.17712 · Cited by 111
Optimal Online Multi-Instance Acquisition in IaaS Clouds
Wang, W., Liang, B., & Li, B. (2014) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2014.2385697 · Cited by 101
Metadata
- Authors
- Karlin, Kenyon, & Randall
- Affiliations
- École Polytechnique (FR)
- Georgia Institute of Technology (US)
- Venue
- Algorithmica
- Published
- 2003-07
- Volume
- 36
- Issue
- 3
- Pages
- 209-224
- ISSN
- 0178-4617 (ISSN-L)
- 1432-0541
- OpenAlex
- W2031816824
- Cited by
- 73
- References
- 8
- Citations by year
- 2024: 2 · 2023: 2 · 2022: 5 · 2021: 5 · 2020: 6 · 2019: 4 · 2018: 3 · 2017: 4 · 2015: 3 · 2014: 3 · 2013: 6 · 2012: 2
- FWCI
- 2.62
- Type
- journal article
- Language
- en
- Open access
- closed
- Licence
- www.springer.com/tdm (tdm)
- Locations
- Algorithmica (publishedVersion)
- Topics
- Physical Sciences › Mathematics › Theoretical Computer Science › Optimization and Search Problems
- Physical Sciences › Mathematics › Theoretical Computer Science › Algorithms and Data Compression
- Social Sciences › Decision Sciences › Management Science and Operations Research › Advanced Bandit Algorithms Research
- Keywords
- ski rental problem, randomized online algorithms, competitive ratio, optimal online algorithms, online decision making
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.