  Relaxing the sequential specification of shared objects has been proposed as
a promising approach to obtain implementations with better complexity. In this
paper, we study the step complexity of relaxed variants of two common shared
objects: max registers and counters. In particular, we consider the
$k$-multiplicative-accurate max register and the $k$-multiplicative-accurate
counter, where read operations are allowed to err by a multiplicative factor of
$k$ (for some $k \in \mathbb{N}$). More accurately, reads are allowed to return
an approximate value $x$ of the maximum value $v$ previously written to the max
register, or of the number $v$ of increments previously applied to the counter,
respectively, such that $v/k \leq x \leq v \cdot k$. We provide upper and lower
bounds on the complexity of implementing these objects in a wait-free manner in
the shared memory model.
