How to proof a heuristic?

Question

I am not very familiar with "heuristic", so please correct me if anything said by me is wrong.

Per my understanding, Algorithm is an automatic steps which guarantee to give a correct solution corresponding to a specific problem (and its input domain)

Heuristic is somehow a rule to guess the next step, hoping when repeating this rule a nearly-optimal solution is found.

---

Algorithm is proof-able, the complexity, the correctness, etc.

But I wonder how can one proof heuristic?

Indeed I wonder is "proof" a correct term / action correlate to heuristic, but how about say, proof the heuristic can give sub-optimal answer (like at most 10% worst than the optimal) for 90% out of all possible input?

Answer 1

According to Wikipedia:

A heuristic technique (...) is any approach to problem solving, learning, or discovery that employs a practical method not guaranteed to be optimal or perfect, but sufficient for the immediate goals.

Thus you can employ a heuristic to design an algorithm. This would give suboptimal answers, however you can still state theorems that relate to the correctness of such algorithm:

• For optimization problems you may write something like:

For any $\epsilon>0$, the algorithm approximates the problem $P$ with a multiplicative factor $1+\epsilon$ in time $O(T(\epsilon))$.

which means that for every input, if the expected answer of $P$ is $y$ and your algorithm returns $y'$, then:

$$y\le y'\le (1+\epsilon)y$$

You can also bound the error with an additive factor for instance.

• For decision problems, if you fix a probability distribution on the input, you may state that your algorithm returns a correct answer with a probability of 90%. That would be a correctness result.

---

In any case you should keep in mind that a heuristic usually denotes general ideas applicable in many situations, which is said to work well empirically and for which you don't try to prove error bounds (such as in simulated annealing).