  Numerous approximation algorithms for problems on unit disk graphs have been
proposed in the literature, exhibiting a sharp trade-off between running times
and approximation ratios. We introduce a variation of the known shifting
strategy that allows us to obtain linear-time constant-factor approximation
algorithms for such problems. To illustrate the applicability of the proposed
variation, we obtain results for three well-known optimization problems. Among
such results, the proposed method yields linear-time (4+eps)-approximation for
the maximum-weight independent set and the minimum dominating set of unit disk
graphs, thus bringing significant performance improvements when compared to
previous algorithms that achieve the same approximation ratios. Finally, we use
axis-aligned rectangles to illustrate that the same method may be used to
derive linear-time approximations for problems on other geometric intersection
graph classes.
