# How to assess performance of an algorithm delivering solutions of varying quality?

I lack formal knowledge about statistics and got lost in the Wikipedia articles about the subject.

I have an algorithm that produces a solution for a problem. There might be several solutions possible. Not all solutions are equally good, and I am able to give score for each solution.

I want to be able to tell if the algorithm is good or not.

For each problem I can calculate bounds on the best and worst possible solution (only bounds, not exact values). I can also generate a random solutions for a problem, but not every random solution is a valid one (high chances for getting a valid one, though).

The data set I am going to use have problems of approximately the same difficulty.

Clearly I should use some statistical test, but which one? It seems that they require knowledge about the distribution and are more suitable for comparing algorithms.

Edit:

I do not want to add too much irrelevant specifics, so I will try to simplify.

I have an algorithm that solves a problem. for example, it finds a path between two nodes in a graph. The input is a graph. The output is a path.

Obviously, shorter paths are better than longer ones.

I want to know if my algorithm is good. I do not know exactly how to define "good", but that is where statistics can help me, is not it?

What I though about so far was to do the following:

1. Run the algorithm on a set of problems (problem is a graph). The sizes of all these graphs are of the same order of magnitude.
2. Find a random path (in my specific problem it is possible to do) for each graph, and do this many times.
3. Compare the results of 1 and 2 to see if my algorithm is better than choosing a path at random.

Am I doing it right? How should I perform step 3?

• I am having great difficulty following this. Can you describe the situation you are studying, the data you have, and the algorithms you are applying? – gung - Reinstate Monica Mar 10 '12 at 3:37
• Are you interested in making some kind of inference about the distribution of solutions that you random solution generator produces? – user9437 Mar 10 '12 at 4:45
• @gung See my edit. – Artium Mar 10 '12 at 22:32
• @jlovegren No. I want to compare the random solution generator to my algorithm and see if mine is better. Also, a-priory I know nothing about the distribution. – Artium Mar 10 '12 at 22:32
• Your answer to @jlovegren suggests that hypothesis testing may not be what you really need. I suspect that your algorithm is better than random & that that can be shown, but that it's not very impressive or meaningful. I will edit to change the tag to machine-learning, as I bet some of those folks will be able to help you. – gung - Reinstate Monica Mar 10 '12 at 22:48

## 1 Answer

I don't think it's too important to know whether or not your method is better than random because there are a number of well-studied algorithms that solve (some specific) graph traversal problems quite well.

I think the more relevant comparison is to ask wether your method is better (1) for some special graph, such as a planar or chromatic graph or (2) for graphs of a certain size or density or number of edges. Note that better can mean any number of things: lower working memory requirements, lower computational complexity, better worst-case behavior, better average behavior.