论文标题
（poly-）对数空间中的近似值
Approximation in (Poly-) Logarithmic Space
论文作者
论文摘要
我们为经典图形开发了新的近似算法，并在空间约束下在RAM模型中设置了问题。作为我们的主要结果之一，我们设计了一种用于D型敲击集的算法，该算法在时间n^{o（d^2 + d/ε}）}中运行，使用O（（D^2 + d/ε）log n）空间位，并实现O（（D/ε）N^^ε）的近似值，以实现任何阳性ε的近似值。特别是，这产生了一个因子-O（log n）近似算法，该算法在时间n^{o（log n）}中运行，并使用o（log^2 n）空间位（用于常数d）。作为推论，我们获得了顶点覆盖物和几个图缺失问题的类似边界。 对于有限的多重问题实例，人们可以做得更好。我们设计了具有最大程度δ的顶点覆盖的因子-2近似算法，以及用于计算最大独立集的算法，该集合在时间n^{o（δ）}中运行，并使用o（Δlogn）空间位。对于更通用的d键设置问题，我们设计了一种因子-D近似算法，该算法在时间n^{o（dδ^2）}中运行，并使用O（dδ^2 log n）位置的o（dδ^2 log n）位置，其中每个元素在大多数ΔSETS中出现在大多数ΔSets中。 对于限制平均度D的图形的独立集，我们给出了一个因子（2D）近似算法，该算法在多项式时间内运行并使用空间的O（log n）位。我们还设计了一个因子n^{o（log n）}的D-De-degenate图上的主导设置的因子-O（d^2）近似算法，并使用o（log^2 n）空间位。对于d-regular图，我们展示了如何将已知的随机因子-O（log d）近似算法推出以在时间n^{o（1）}中运行并使用空间的O（log n）位。 我们的结果结合了内核理论，分布式算法和随机算法的组合。
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.
