Approximation in (poly-) logarithmic space
Journal article, Peer reviewed
Published version
![Thumbnail](/bora-xmlui/bitstream/handle/11250/2763885/LIPIcs-MFCS-2020-16.pdf.jpg?sequence=6&isAllowed=y)
Åpne
Permanent lenke
https://hdl.handle.net/11250/2763885Utgivelsesdato
2020Metadata
Vis full innførselSamlinger
- Department of Informatics [978]
- Registrations from Cristin [10237]
Originalversjon
Leibniz International Proceedings in Informatics. 2020, 170, 16. 10.4230/LIPIcs.MFCS.2020.16Sammendrag
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 nO(d2+(d/ε)), uses O(d2 + (d/ε)) log n) bits of space, and achieves an approximation ratio of O((d/ε)nε) for any positive ε ≤ 1 and any constant d ∈ N. In particular, this yields a factor-O(d log n) approximation algorithm which uses O(log2 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(d2) approximation algorithm for Dominating Set on d-degenerate graphs which runs in time nO(log n) and uses O(log2 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.