Voting algorithms for unique games on complete graphs

An approximation algorithm for a Constraint Satisfaction Problem is called robust if it outputs an assignment satisfying a $(1 - f(\epsilon))$-fraction of the constraints on any $(1-\epsilon)$-satisfiable instance, where the loss function $f$ is such that $f(\epsilon) \rightarrow 0$ as $\epsilon \rightarrow 0$. Moreover, the runtime of the algorithm should not depend in any way on $\epsilon$. In this paper, we present such an algorithm for {\sc Min-Unique-Games(q)} on complete graphs with $q$ labels. Specifically, the loss function is $f(\epsilon) = (\epsilon + c_{\epsilon} \epsilon^2)$, where $c_{\epsilon}$ is a constant depending on $\epsilon$ such that $\lim_{\epsilon \rightarrow 0} c_{\epsilon} = 16$. The runtime of our algorithm is $O(qn^3)$ (with no dependence on $\epsilon$) and can run in time $O(qn^2)$ using a randomized implementation with a slightly larger constant $c_{\epsilon}$. Our algorithm is combinatorial and uses voting to find an assignment. We prove NP-hardness (using a randomized reduction) for {\sc Min-Unique-Games(q)} on complete graphs even in the case where the constraints form a cyclic permutation, which is also known as {\sc Min-Linear-Equations-mod-$q$} on complete graphs.