8
$\begingroup$

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.

  1. Is my solution a heuristic or approximation?

  2. 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

$\endgroup$
  • $\begingroup$ You first need to define what you want to approximate in order to judge whether your approach is an approximation. $\endgroup$ – Dan Mar 1 '13 at 18:53
  • $\begingroup$ What exactly is the optimization problem you are trying to solve? Once that is known then if you prove bounds your heuristic becomes an approximation. Additionally, the only (classical, ie, non-streaming) problems in P that have approximation algorithms (that I know of) are max-flow algorithms. $\endgroup$ – Nicholas Mancuso Mar 1 '13 at 18:53
  • $\begingroup$ ok so the thing the i wish to calculate are the numbers within the second array. but this is takes too long , however I figured out that if I add two consecutive values of array 1 together i get something ok and i can prove that the estimation will always be within +-x. initial alg for computing A[j] is O(n^100) $\endgroup$ – user6697 Mar 1 '13 at 19:08
  • $\begingroup$ I understand you want to compute the numbers in the second array, but what is the optimization problem formulation. Given X compute Y under the constraints of Z. Saying you want to compute some arbitrary function does not help. $\endgroup$ – Nicholas Mancuso Mar 1 '13 at 19:19
  • $\begingroup$ Your solution is a perfect example of a heuristic! $\endgroup$ – Björn Lindqvist Nov 26 '18 at 16:05
10
$\begingroup$

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 <some parameters that can be varied> the solution is never worse than optimal by more than a factor $1 + \epsilon$, where $\epsilon$ depends on <parameters>).

$\endgroup$
  • 1
    $\begingroup$ You used bad sample, TSP is hard to approximate, so there is no PTAS for TSP also there is no 2 approximation for TSP is easy to show if there is polynomial time 2-approximation for TSP there is polynomial time algorithm for solving hamiltonian cycle problem, I think you mean metric TSP which is special case but still there is no PTAS in this case (and proved is impossible to have PTAS except P=NP). I would suggest to choose bin packing for talking about this. (or any other simpler problem). $\endgroup$ – user742 Mar 2 '13 at 3:39
  • $\begingroup$ @SaeedAmiri, it was just for illustration purposes. Perhaps not the best example (as you state), but the problem is easy to understand. Thanks for the comment. $\endgroup$ – vonbrand Mar 2 '13 at 3:45
  • $\begingroup$ So if you understand this is wrong example why you don't fix it? $\endgroup$ – user742 Mar 2 '13 at 4:30
  • $\begingroup$ @SaeedAmiri I think it is totally fine. Remember we don't know if for example $\mathsf{P}=\mathsf{NP}$, for which hardness of approximation can be based on. $\endgroup$ – Juho Mar 2 '13 at 22:47
  • $\begingroup$ @Juho, by my knowledge is totally wrong even by knowing that we don't know $P=NP$, the main point is may be is in reveres direction ($P\not =NP$), So we shouldn't use bad samples, we should use samples that we know they are correct independent from things we don't know. $\endgroup$ – user742 Mar 6 '13 at 9:47
6
$\begingroup$

You can see this very interesting answer about Heuristic in Wikipedia:

" a heuristic is a technique designed for solving a problem more quickly when classic methods are too slow. The objective of a heuristic is to produce quickly enough a solution that is good enough for solving the problem at hand. ".

Heuristic could derive from theory or experimental experience, but approximation algorithms have solid theory foundation (provable solution).

$\endgroup$
4
$\begingroup$

As for your last question, there is no separate theory for approximation algorithms for problems that are solvable in polynomial time. In fact, it might be that $\mathsf{P}=\mathsf{NP}$. Some examples of approximation algorithms for problems in $\mathsf{P}$ include algorithms for numerical linear algebra and computational geometry. See the question Approximation algorithms for problems in P for more.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.