Abstract
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² + (d / ε))}, uses O(d² + (d / ε) log n) bits of space, and achieves an approximation ratio of O((d / ε) n^ε) for any positive ε ≤ 1 and any constant d ∈ ℕ. In particular, this yields a factorO(d log n) approximation algorithm which uses O(log² 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 Δ, one can do better. We give a factor2 approximation algorithm for Vertex Cover which runs in time n^{O(Δ)} and uses O(Δ 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 factorO(d²) approximation algorithm for Dominating Set on ddegenerate graphs which runs in time n^{O(log n)} and uses O(log² n) bits of space. For dregular graphs, we observe that a known randomized algorithm which achieves an approximation ratio of O(log d) can be derandomized 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.
BibTeX  Entry
@InProceedings{biswas_et_al:LIPIcs:2020:12685,
author = {Arindam Biswas and Venkatesh Raman and Saket Saurabh},
title = {{Approximation in (Poly) Logarithmic Space}},
booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
pages = {16:116:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771597},
ISSN = {18688969},
year = {2020},
volume = {170},
editor = {Javier Esparza and Daniel Kr{\'a}ľ},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12685},
URN = {urn:nbn:de:0030drops126852},
doi = {10.4230/LIPIcs.MFCS.2020.16},
annote = {Keywords: approximation, logspace, logarithmic, log, space, small, limited, memory, ROM, readonly}
}
Keywords: 

approximation, logspace, logarithmic, log, space, small, limited, memory, ROM, readonly 
Collection: 

45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) 
Issue Date: 

2020 
Date of publication: 

18.08.2020 