论文标题
套件盖和相关问题的次指数时间近似的紧密界限
Tight Bounds on Subexponential Time Approximation of Set Cover and Related Problems
论文作者
论文摘要
我们显示，对于任何$ 0 <γ<1 $和任何$Δ> 0 $，假设$ 0 <γ<1 $，则在时间exp（$ n^{γ-δ}）$的$（1-γ）\ ln n $ factor中近似于$ n $元素的设置盖。这本质上与Cygan等人（IPL，2009）$（1-γ）\ ln n $ factor in Time $ exp（O（n^γ））$中的最佳上限相匹配。 通过从标签覆盖物中提取独立的减少到Moshkovitz（计算理论，2015年）的工作，并将其应用于与那里的其他PCP定理，从而获得了下限。在投射游戏猜想的调理时，我们还会获得更严格的下限。 我们还严格概括了设置盖，我们还将三个问题（定向的施泰纳树，下覆盖和连接的多膜化）处理。对于任何$ 1/2 \leγ<1 $，我们给出了这些问题的$（1-γ）\ ln n $ -approximation算法。
We show that Set Cover on instances with $N$ elements cannot be approximated within $(1-γ)\ln N$-factor in time exp($N^{γ-δ})$, for any $0 < γ< 1$ and any $δ> 0$, assuming the Exponential Time Hypothesis. This essentially matches the best upper bound known by Cygan et al.\ (IPL, 2009) of $(1-γ)\ln N$-factor in time $exp(O(N^γ))$. The lower bound is obtained by extracting a standalone reduction from Label Cover to Set Cover from the work of Moshkovitz (Theory of Computing, 2015), and applying it to a different PCP theorem than done there. We also obtain a tighter lower bound when conditioning on the Projection Games Conjecture. We also treat three problems (Directed Steiner Tree, Submodular Cover, and Connected Polymatroid) that strictly generalize Set Cover. We give a $(1-γ)\ln N$-approximation algorithm for these problems that runs in $exp(\tilde{O}(N^γ))$ time, for any $1/2 \le γ< 1$.
