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 constant d\in N . In particular, this yields a factor-O( d log n) approximation algorithm which  uses O(log^2 n) bits of space  . As a corollary, we obtain similar bounds on space and approximation ratio for Vertex Cover and several graph deletion problems. For graphs with maximum degree \Delta , one can do better. We give a factor-2 approximation algorithm for Vertex Cover which runs in time n^{O(\Delta)} and uses O(\Delta log n) bits of space. For Independent Set on } 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 observe that a known randomized algorithm which achieves an approximation ratio of O (log d)  can be derandomized and implemented to run in polynomial time 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.
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) 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 \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.
D
(
D
))
A
)
A
(
D
(
R
\epsilon
\epsilon
R
constant d\in N
natural number d
D
d
A
runs in time n^{O(log n)
A
(for constant d)
D
on space and approximation ratio
R
graphs with maximum degree \Delta
bounded-multiplicity problem instances
R
give
devise
R
which runs
on graphs with maximum degree \Delta, and an algorithm for computing maximal independent sets which both run
R
uses
use
R
Independent Set on
the more general d-Hitting Set problem, we devise a factor-d approximation algorithm which runs in time n^{O(d {\delta
A
\delta
A
^2 log n) bits of space on set families where each element appears in at most \delta sets. For Independent Set restricted to
R
observe that
show how
R
algorithm which achieves an approximation ratio of O
factor-O
A
approximation algorithm
D
and implemented
R
polynomial time
time n^{O(1)