Voting algorithms for unique games on complete graphs

Antoine Méot, Arnaud de Mesmay, Moritz Mühlenthaler +1

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 )$-s…