Tight Bounds on Online Checkpointing Algorithms

摘要: The problem of online checkpointing is a classical with numerous applications which had been studied in various forms for almost 50 years. In the simplest version this problem, user has to maintain $k$ memorized checkpoints during long computation, where only allowed operation move one from its old time current time, and his goal keep as evenly spread out possible at all times. Bringmann et al. special case an online/offline optimization deviation uniformity measured by natural discrepancy metric worst ratio between real ideal segment lengths. They showed smaller than $1.59-o(1)$ $k$, $\ln4-o(1)\approx1.39$ sparse subset $k$'s are powers 2. addition, they obtained upper bounds on achievable some small values $k$. In paper we solve main problems left open above-mentioned proving that $\ln4$ tight lower bound asymptotic large providing (in form provably optimal algorithms, fact better those Bringmann al.) $k \leq 10$. last part describe new problem.