Heuristic certificates via approximations

This paper suggests a new framework in which the quality of a (not necessarily optimal) heuristic solution is certified by an approximation algorithm. Namely, a result of a heuristic solution is accompanied by a scale obtained from an approximation algorithm. The creation of a scale is efficient while getting a solution from an approximation algorithm is usually concerned with long calculation relatively to heuristics approach. On the other hand, a result obtained by heuristics without scale might be useless. The criteria for choosing an approximation scheme for producing a scale have been investigated. To obtain a scale in practice, not only approximations have been examined by their asymptotic behavior but also relations as a function of an input size of a given problem. For study case only, heuristic and approximation algorithms for the SINGLE KNAPSACK, MAX 3-SAT, and MAXIMUM BOUNDED THREE-DIMENSIONAL MATCHING (MB3DM) NP-hard problems have been examined. The certificates for the heuristic runs have been obtained by using fitting approximations.