Tight Bounds on Online Checkpointing Algorithms

摘要: The problem of online checkpointing is a classical with numerous applications that has been studied in various forms for almost 50 years. In the simplest version this problem, user 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, Doerr, Neumann, Sliacan special case an online/offline optimization which deviation uniformity measured by natural discrepancy metric worst ratio between real ideal segment lengths. They showed smaller than 1.59-o(1) ln 4-o(1)≈ 1.39 sparse subset k’s, are powers 2. addition, they obtained upper bounds on achievable some small values k. article, we solve main problems left open above-mentioned paper proving 4 tight lower bound asymptotic large providing (in form provably optimal algorithms, fact better those Bringmann et al.) ≤ 10. last part describe new problem.