arXiv preprint ·
Ski Rental with Uniform Stochastic Signals
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Ski rental is one of the most fundamental online problems, where an agent repeatedly decides whether it should continue renting for a service, or buy it at a one-time fixed cost. In classic online analysis, an adversary may freely select any arbitrary time horizon $t$ after which the instance terminates, hence leading to strong competitive ratio lower bounds of 2 (deterministic) and $e/(e-1)$ (randomized). We consider a novel but natural model aiming at limiting the adversary's power without degrading its flexibility. A stochastic signal, containing no information apart from its arrival time, is transmitted to the algorithm at a time drawn from a known distribution scaled to $[0,t]$. This framework allows us to account for visible effects of the adversary's choice to the algorithm. Focusing as a first step on uniform distributions, we show that the best possible competitive ratios are approximately $1.478$ (deterministic) and $1.438$ (randomized). Surprisingly, simplistic deterministic strategies already achieve a performance of $1.489$.
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
Hadamard Transforms for Dimension Reduction
Approximating Directed Telephone Multicast
Exact minimum Birkhoff decompositions of doubly stochastic matrices with finite precision
A 55-Addition Rank-23 Scheme for $3\times3$ Matrix Multiplication via Exact Two-Sided Minimization
Integer Programing: An Algorithm with Exponent Linear in the Dimension
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.