  We consider the machine covering problem for selfish related machines. For a
constant number of machines, m, we show a monotone polynomial time
approximation scheme (PTAS) with running time that is linear in the number of
jobs. It uses a new technique for reducing the number of jobs while remaining
close to the optimal solution. We also present an FPTAS for the classical
machine covering problem (the previous best result was a PTAS) and use this to
give a monotone FPTAS.
  Additionally, we give a monotone approximation algorithm with approximation
ratio \min(m,(2+\eps)s_1/s_m) where \eps>0 can be chosen arbitrarily small and
s_i is the (real) speed of machine i. Finally we give improved results for two
machines.
  Our paper presents the first results for this problem in the context of
selfish machines.
