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