Back to Search
Start Over
Guessing fractions of online sequences
- Source :
- Discrete Applied Mathematics. 308:147-161
- Publication Year :
- 2022
- Publisher :
- Elsevier BV, 2022.
-
Abstract
- An online algorithm is typically unaware of the length of the input request sequence that it is called upon. Consequently, it cannot determine whether it has already processed most of its input or whether the bulk of work is still ahead. In this paper, we are interested in whether some sort of orientation within the request sequence is nevertheless possible. For a real number 0 f 1 , our objective is to preemptively guess the position f n within the request sequence of unknown length n : While processing the input, the online algorithm maintains a guess and is only allowed to update its guess to the position of the current element under investigation. We give a complete characterization of the optimal guessing strategies with respect to f : For f ≤ f 0 ≈ 0 . 1867 , the trivial algorithm that never updates its initial guess is (asymptotically) optimal. For f > f 0 , we give a randomized algorithm that in expectation places the guess at distance β ( f ) n from f n , where β is a non-elementary function, and we prove that this is optimal. Our findings show that the position f max n ≈ 0 . 2847 n is hardest to guess. We also give upper and lower bounds for a natural extension to weighted sequences. Our work can also be seen as the first randomized approach to the online checkpointing problem.
- Subjects :
- Sequence
Applied Mathematics
0211 other engineering and technologies
021107 urban & regional planning
0102 computer and information sciences
02 engineering and technology
Function (mathematics)
Characterization (mathematics)
01 natural sciences
Upper and lower bounds
Randomized algorithm
Combinatorics
010201 computation theory & mathematics
Position (vector)
Discrete Mathematics and Combinatorics
Online algorithm
Mathematics
Real number
Subjects
Details
- ISSN :
- 0166218X
- Volume :
- 308
- Database :
- OpenAIRE
- Journal :
- Discrete Applied Mathematics
- Accession number :
- edsair.doi...........17cf7b9ea76601488311f8ef8ad55c72