License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2020.16
URN: urn:nbn:de:0030-drops-126852
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12685/
Biswas, Arindam ;
Raman, Venkatesh ;
Saurabh, Saket
Approximation in (Poly-) Logarithmic Space
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 factor-O(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 factor-2 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 factor-O(d²) approximation algorithm for Dominating Set on d-degenerate graphs which runs in time n^{O(log n)} and uses O(log² 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 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:1--16:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-159-7},
ISSN = {1868-8969},
year = {2020},
volume = {170},
editor = {Javier Esparza and Daniel Kr{\'a}ľ},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12685},
URN = {urn:nbn:de:0030-drops-126852},
doi = {10.4230/LIPIcs.MFCS.2020.16},
annote = {Keywords: approximation, logspace, logarithmic, log, space, small, limited, memory, ROM, read-only}
}
|
Keywords: |
|
approximation, logspace, logarithmic, log, space, small, limited, memory, ROM, read-only |
|
Collection: |
|
45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
18.08.2020 |
