Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Online Checkpointing with Improved Worst-Case Guarantees   In the online checkpointing problem, the task is to continuously maintain a
set of k checkpoints that allow to rewind an ongoing computation faster than by
a full restart. The only operation allowed is to replace an old checkpoint by
the current state. Our aim are checkpoint placement strategies that minimize
rewinding cost, i.e., such that at all times T when requested to rewind to some
time t <= T the number of computation steps that need to be redone to get to t
from a checkpoint before t is as small as possible. In particular, we want that
the closest checkpoint earlier than t is not further away from t than q_k times
the ideal distance T / (k+1), where q_k is a small constant.
  Improving over earlier work showing 1 + 1/k <= q_k <= 2, we show that q_k can
be chosen asymptotically less than 2. We present algorithms with asymptotic
discrepancy q_k <= 1.59 + o(1) valid for all k and q_k <= ln(4) + o(1) <= 1.39
+ o(1) valid for k being a power of two. Experiments indicate the uniform bound
p_k <= 1.7 for all k. For small k, we show how to use a linear programming
approach to compute good checkpointing algorithms. This gives discrepancies of
less than 1.55 for all k < 60.
  We prove the first lower bound that is asymptotically more than one, namely
q_k >= 1.30 - o(1). We also show that optimal algorithms (yielding the infimum
discrepancy) exist for all k.

29
The categories of this paper are: funct-an
16
The categories of this paper are: stat
20
The categories of this paper are: acc-phys
0
The categories of this paper are: hep-ph
34
The categories of this paper are: chem-ph
4
The categories of this paper are: cond-mat
36
The categories of this paper are: cmp-lg
24
The categories of this paper are: dg-ga
6
The categories of this paper are: astro-ph
9
The categories of this paper are: nlin
15
The categories of this paper are: nucl-ex
8
The categories of this paper are: hep-ex
37
The categories of this paper are: supr-con
26
The categories of this paper are: bayes-an
2
The categories of this paper are: math
27
The categories of this paper are: comp-gas