论文标题
偏置CSP的近似性的表征
A Characterization of Approximability for Biased CSPs
论文作者
论文摘要
带有谓词$ψ的$ $ $ $偏见的max-csp实例：\ {0,1 \}^r \ to \ {0,1 \} $是约束满意度问题（CSP）的一个实例，目的是在其中找到相对权重的标签，最多满足约束的最大分数。有偏见的CSP具有通用性，并表达了几个经过深入研究的问题，例如密度 - $ k $ -sub（hyper）图和SmallSetExpansion。 在这项工作中，我们探讨了偏见参数$μ$在偏见CSP的近似性上所起的作用。我们表明，可以使用密度 - $ K $ -Subhypergergraph（dksh）的偏置 - 及时曲线（dksh）来表征此类CSP的近似性（最多达到Arity $ r $的损失）。特别是，这给出了谓词的严格表征，该谓词承认近似保证与偏置参数$μ$无关。 在以上的动机上，我们为DKSH提供了新的近似值和硬度结果。特别是，假设小型扩展假设（SSEH），我们表明，对于每个$ r \ geq 2 $ r \ geq 2 $和$ r \ geq 2 $ and $ r \ geq 2 $和$ r \ geq 2 $和$ r \ geq 2 $ and $ r \ r^3μ^{r-1} \ log（1/μ），dksh arity $ r $和$ r $和$ k =μn$大约为$ω（r^3μ^{r-1} \ log（1/μ））$。我们还给出了$ O（μ^{r-1} \ log（1/μ））$ - 相同设置的近似算法。当Arity $ r $是一个恒定的情况下，我们的上限和下限都紧密到不变的因素，尤其是在线性偏置方案中最密集的-1 $ K $ -SUBGRAPH问题的第一个紧密近似范围。此外，使用上述表征，我们的结果还意味着每种有偏见的CSP的恒定CSP匹配算法和硬度。
A $μ$-biased Max-CSP instance with predicate $ψ:\{0,1\}^r \to \{0,1\}$ is an instance of Constraint Satisfaction Problem (CSP) where the objective is to find a labeling of relative weight at most $μ$ which satisfies the maximum fraction of constraints. Biased CSPs are versatile and express several well studied problems such as Densest-$k$-Sub(Hyper)graph and SmallSetExpansion. In this work, we explore the role played by the bias parameter $μ$ on the approximability of biased CSPs. We show that the approximability of such CSPs can be characterized (up to loss of factors of arity $r$) using the bias-approximation curve of Densest-$k$-SubHypergraph (DkSH). In particular, this gives a tight characterization of predicates which admit approximation guarantees that are independent of the bias parameter $μ$. Motivated by the above, we give new approximation and hardness results for DkSH. In particular, assuming the Small Set Expansion Hypothesis (SSEH), we show that DkSH with arity $r$ and $k = μn$ is NP-hard to approximate to a factor of $Ω(r^3μ^{r-1}\log(1/μ))$ for every $r \geq 2$ and $μ< 2^{-r}$. We also give a $O(μ^{r-1}\log(1/μ))$-approximation algorithm for the same setting. Our upper and lower bounds are tight up to constant factors, when the arity $r$ is a constant, and in particular, imply the first tight approximation bounds for the Densest-$k$-Subgraph problem in the linear bias regime. Furthermore, using the above characterization, our results also imply matching algorithms and hardness for every biased CSP of constant arity.
