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/��})}, uses O((d^2 + d/��) log n) bits of space, and achieves an approximation ratio of O((d/��) n^��) for any positive ��\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 ��, and an algorithm for computing maximal independent sets which both run in time n^{O(��)} and use O(��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 ��^2)} and uses O(d ��^2 log n) bits of space on set families where each element appears in at most ��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.

MFCS 2020