arXiv preprint ·
A Sharp Additive Bound for the Threshold Rule in Repeated Rent-or-Buy
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Motivated by context management in LLM agents, we study a repeated rent-or-buy model with schedule-independent history growth and a fixed reset price $K$, a discrete form of dynamic TCP acknowledgment: every call pays as rent the history accumulated since the last reset, and a reset clears it. The classical threshold rule is $2$-competitive, and no deterministic rule guarantees a smaller ratio. We show that, measured additively, its loss is governed by the changes in the growth: if the growth is constant on $P$ runs, the threshold rule, knowing neither the runs nor the horizon, pays at most $(2P-1)K$ more than the optimal schedule chosen with hindsight, and the coefficient $2P-1$ is sharp. If the growth is only within a factor $1+\varepsilon$ of $P$ runs, the bound holds up to a factor $1+\varepsilon$ and an extra $\varepsilon K$. The proof is a potential argument built from the relative value functions of the single-rate problems. On two runs no deterministic rule guarantees a loss below $2K$. A rule that also resets when the growth decreases guarantees $2K$, while the threshold rule can lose arbitrarily close to $3K$.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
A Constant-Factor Approximation for Capacitated Facility Location with Outliers
Noncrossing is All You Need: Beyond Identical Delay Functions in Online Matching with Delays on General Metrics
Semidirect sums of tensors and the matrix multiplication exponent
Sublinear Metric Distortion for Matching
Incremental Open Addressing Has No Time-Space Tradeoff
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.