Difference between heuristic and approximation algorithm? i have a problem regarding the following situation. 

I have two arrays of numbers like this:

index/pos     0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15 
Array 1(i):   1   2   3   4   7   5   4   3   7   6   5   1   2   3   4   2
Array 2(j):   4   4   8  10  10   7   7  10  10  11   7   4   7   7   4


now suppose the second array is very hard to compute but I have noticed that if I add  

A[i] + A[i+1]

in the array 1 I get the number very close to the number A[j] in the array 2. 


Is my solution a heuristic or approximation?
If I had a reason to believe that I will never overshoot the value of A[j] by +-x with this algorithm and can prove it, would then  my solution be a heuristic or approximation?


Is there any literature that deals with heuristic vs. approximation questions for P class problems where the solution can be achieved in polynomial time but the input is just too big for a poly time algorithm to be practical.

thank you
A heuristic is essentially a hunch, i.e., the case you describe ("I noticed it is near", you don't have a proof it is so) is a heuristic. As is solving the traveling salesman problem by starting at a random vertex and going to the nearest not yet visited each step. It is a plausible idea, that should not give a too bad solution. In this case, it can be shown that it won't always give a good solution.

An approximation algorithm is usually understood to give an approximate solution, with some kind of guarantee of performance (i.e., it solves TSP, and the total cost is never off by more than a factor of 2; or even better, it solves TSP and, depending on &lt;some parameters that can be varied&gt; the solution is never worse than optimal by more than a factor $1 + \epsilon$, where $\epsilon$ depends on &lt;parameters&gt;).