  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 a robust algorithm should not depend in any way on
$\epsilon$. In this paper, we present such an algorithm for Min-Unique-Games 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. It can furthermore be used
to provide a PTAS for Min-Unique-Games on complete graphs, recovering a result
of Karpinski and Schudy with a simpler algorithm and proof. We also prove
NP-hardness for Min-Unique-Games on complete graphs and (using a randomized
reduction) even in the case where the constraints form a cyclic permutation,
which is also known as Min-Linear-Equations-mod-$q$ on complete graphs.
