  We consider the Ruderman-Kittel-Kasuya-Yosida (RKKY) interaction between
magnetic impurities on the surface of a three-dimensional topological insulator
with proximity induced superconductivity. A superconductor placed on the top of
the topological insulator induces a gap in the surface electron states and
gives rise to a long-ranged in-plane antiferromagnetic RKKY interaction. This
interaction is frustrated due to strong spin-orbit coupling, decays as $1/r$
for $r<\xi$, where $r$ is the distance between two magnetic impurities and
$\xi$ the superconducting coherence length, and dominates over the
ferromagnetic and Dzyaloshinskii-Moriya type interactions for $r>\xi$. We find
the condition for the Yu-Shiba-Rusinov intragap states that are bound to the
magnetic impurities.
