Revised: November 7, 2021
Published: February 14, 2022
Abstract: [Plain Text Version]
We prove almost optimal hardness for $\maxx$ $k$-$\csp_R$. In $\maxx$ $k$-$\csp_R$, we are given a set of constraints, each of which depends on at most $k$ variables. Each variable can take any value from $1, 2, \dots, R$. The goal is to find an assignment to variables that maximizes the number of satisfied constraints.
We show that, for any $k \geq 2$ and $R \geq 16$, it is NP-hard to approximate $\maxx$ $k$-$\csp_R$ to within factor $k^{O(k)}(\log R)^{k/2}/R^{k - 1}$. In the regime where $3 \leq k = o(\log R/\log \log R)$, this ratio improves upon Chan's $O(k/R^{k-2})$ factor NP-hardness of approximation of $\maxx$ $k$-$\csp_R$ (J. ACM 2016). Moreover, when $k = 2$, our result matches the best known hardness result of Khot, Kindler, Mossel and O'Donnell (SIAM J. Comp. 2007). We remark here that NP-hardness of an approximation factor of $2^{O(k)}\log(kR)/R^{k - 1}$ is implicit in the (independent) work of Khot and Saket (ICALP 2015), which is better than our ratio for all $k \geq 3$.
In addition to the above hardness result, by extending an algorithm for $\maxx$ $2$-$\csp_R$ by Kindler, Kolla and Trevisan (SODA 2016), we provide an $\Omega(\log R/R^{k - 1})$-approximation algorithm for $\maxx$ $k$-$\csp_R$. Thanks to Khot and Saket's result, this algorithm is tight up to a factor of $O(k^2)$ when $k \leq R^{O(1)}$. In comparison, when $3 \leq k$ is a constant, the previously best known algorithm achieves an $O(k/R^{k - 1})$-approximation for the problem, which is a factor of $O(k \log R)$ from the inapproximability ratio in contrast to our gap of $O(k^2)$.
-----------------
A conference version of this paper appeared in the Proceedings of the 19th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'16).
Licensed under a Creative Commons Attribution License (CC-BY)