Optimal Inapproximability of Generalized Linear Equations over a Finite Group
It identifies a rare predicate that is approximation resistant on almost satisfiable instances but admits a non-trivial approximation on satisfiable instances, advancing the understanding of CSP approximability.
The paper studies constraint satisfaction problems with generalized linear equations over a finite group, providing an optimal approximation algorithm for satisfiable instances and proving inapproximability for certain sets S under P≠NP.
Constraint satisfaction problems (CSPs) consist of a set of variables taking values from some finite domain and a set of local constraints on these variables. The objective is to find an assignment to the variables that maximizes the fraction of satisfied constraints. In this work, we study the CSP where the constraints are generalized linear equations over a finite group G. More specifically, for a given $S \subseteq G$, the constraints in this CSP are of the form addition of the values to the variables (similarly, product for non-abelian groups), belonging to the set $S$. We give an approximation algorithm for this problem on satisfiable instances and show that it is optimal for certain $S$ assuming $P\neq NP$. This natural predicate is one of the very few known predicates that are approximation resistant on almost satisfiable instances, assuming $P\neq NP$, but admits a non-trivial approximation algorithm on satisfiable instances.