How to label a performance profile A performance profile is a particular type of plot popular in optimization. Basically, for each ratio R on the x axis, the y axis shows what is the fraction of the number of total tests that were solved within a ratio R of the best result, under a certain performance measure. See for instance this blog entry for an introduction, or Section 22.4 of Higham and Higham's book Matlab guide.

For instance, in the picture below, the blue algorithm gives the best result on about 95% of the examples, and solves the remaining ones within a factor of about 1.2 of the best algorithm.



What is the clearest way to label the axes of such a plot?

I have included an attempt above, but it might be too verbose for a label. The linked blog uses "problems solved" and "performance ratio". Higham and Higham use no axis labels. Other sources put unenlightening letters such as $\theta$ on the x axis.
Most people call this "cumulative distribution function", or "CDF". A Google image search for "cdf performance" produces many plots of this type with the vertical axes labeled "CDF", which should be understood by people in the field if the field is "mathematically inclined" enough.

A more verbose way for more divulgative works is to label the horizontal axis


Ratio to best performance, r


and the vertical axis 


Probability of achieving a (performance) ratio &lt; r.


An additional difficulty of your example is that the measure "ratio to best performance" is not easy to explain in very few words. In such cases, a good idea is to use the caption of the figure to further clarify what the axis labels mean. This way, those who do not understand the labels can quickly get more information from the caption.