  We develop new approximation algorithms for classical graph and set problems
in the RAM model under space constraints. As one of our main results, we devise
an algorithm for d-Hitting Set that runs in time n^{O(d^2 + d/\epsilon})}, uses
O((d^2 + d/\epsilon) log n) bits of space, and achieves an approximation ratio
of O((d/{\epsilon}) n^{\epsilon}) for any positive \epsilon \leq 1 and any
natural number d. In particular, this yields a factor-O(log n) approximation
algorithm which runs in time n^{O(log n)} and uses O(log^2 n) bits of space
(for constant d). As a corollary, we obtain similar bounds for Vertex Cover and
several graph deletion problems.
  For bounded-multiplicity problem instances, one can do better. We devise a
factor-2 approximation algorithm for Vertex Cover on graphs with maximum degree
\Delta, and an algorithm for computing maximal independent sets which both run
in time n^{O(\Delta)} and use O(\Delta log n) bits of space. For the more
general d-Hitting Set problem, we devise a factor-d approximation algorithm
which runs in time n^{O(d {\delta}^2)} and uses O(d {\delta}^2 log n) bits of
space on set families where each element appears in at most \delta sets.
  For Independent Set restricted to graphs with average degree d, we give a
factor-(2d) approximation algorithm which runs in polynomial time and uses
O(log n) bits of space. We also devise a factor-O(d^2) approximation algorithm
for Dominating Set on d-degenerate graphs which runs in time n^{O(log n)} and
uses O(log^2 n) bits of space. For d-regular graphs, we show how a known
randomized factor-O(log d) approximation algorithm can be derandomized to run
in time n^{O(1)} and use O(log n) bits of space.
  Our results use a combination of ideas from the theory of kernelization,
distributed algorithms and randomized algorithms.
