























Inapproximability results for $\mathsf{Max\,k\,CSP\!-\!q}$ have been traditionally established using balanced $t$-wise independent distributions, which are closely related to orthogonal arrays, a famous family of combinatorial designs. In this work, we investigate the role of these combinatorial structures in the context of the differential approximability of $\mathsf{k\,CSP\!-\!q}$, providing new structural insights and approximation bounds. We first establish a direct connection between the average differential ratio on $\mathsf{k\,CSP\!-\!q}$ instances and orthogonal arrays. This allows us to derive the new differential approximability bounds of $1/q^k$ for $(k +1)$-partite instances, $Ω(1/n^{\lfloor k/2\rfloor})$ for Boolean instances, $Ω(1/n)$ when $k =2$, and $Ω(1/n^{k -\lceil\log_{Θ(q)}k\rceil})$ when $k, q\geq 3$. We then introduce families of array pairs, called {\em alphabet reduction pairs of arrays}, that are still related to balanced $k$-wise independence. Using these pairs of arrays, we establish a reduction from $\mathsf{k\,CSP\!-\!q}$ to $\mathsf{k\,CSP\!-\!k}$ (where $q >k$), with an expansion factor of $1/(q -k/2)^k$ on the differential approximation guarantee. Combining this with a 1998 result by Yuri Nesterov, we conclude that $\mathsf{2\,CSP\!-\!q}$ is approximable within a differential factor of $0.429/(q -1)^2$. Finally, using similar Boolean array pairs, {\em called cover pairs of arrays}, we prove that every Hamming ball of radius $k$ provides a $Ω(1/n^k)$-approximation of the instance diameter. Thus, our work highlights the relevance of combinatorial designs for establishing structural differential approximation guarantees for CSPs.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。