According to Wikipedia,A $\rho$-approximation algorithm $A$ is defined to be an algorithm for which it has been proven that the value/cost, $f(x)$, of the approximate solution $A(x)$ to an instance $x$ will not be more (or less, depending on the situation) than a factor $\rho$ times the value, $OPT$, of an optimum solution.I am interested in a situation where we would like to measure the performance of $A$ by how often it finds the optimal solution. For example, the algorithm $A$ finds the optimal value $R$ % of the time and finds a strictly larger (or less) solution $100-R$ % of the time. What would such algorithm be called? Is this notion known in the literature?
What would you call an algorithm that finds $R$ % of the time the optimal solution to an NP-hard problem?
terminology;reference request