Informatics and Applications
2015, Volume 9, Issue 1, pp 1527
HEURISTIC CERTIFICATES VIA APPROXIMATIONS
 Sh. Dolev
 M. KoganSadetsky
Abstract
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 3SAT, and
MAXIMUM BOUNDED THREEDIMENSIONAL MATCHING (MB3DM) NPhard problems have been
examined. The certificates for the heuristic runs have been obtained by using fitting approximations.
[+] References (15)
 Holland, J. 1971. Genetic algorithms and the optimal
allocation of trials. SIAM J. Comput. 2:88105.
 Wall, M., and MIT. 19942005. GAlib: A C++ library
of genetic algorithm components. Available at: http://
lancet.mit.edu/ga/ (accessed February 10, 2015).
 Kellerer, H.,U. Pferschy, and D. Pisinger. 2004. Knapsack
problems. Berlin: Springer. 161166.
 http://www.cs.bgu.ac.il/~sadetsky/Thesis/ (accessed
February 10, 2015).
 Sipper, M. 1996. A brief introduction to genetic algorithms.
Available at: http://www.cs.bgu.ac.il/ˇ«sipper/
ga.html (accessed February 10, 2015).
 Trevisan, L. 1997. Reductions and (non)approximability.
Universita Degli Studi di Roma "La Sapienza", dotoorato
di Rjcerca in Informatica. IX977:1735.
 Ausiello, G., and V. Th. Paschos. 2005. Approximability
preserving reductions. Cahier Du Lamsade 227:12.
 Hastad, J. 1997. Some optimal inapproximability results.
29th ACMS ymposium on Theory of Computing Proceedings.
110.
 http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/cla
ss/15451s00/www/lectures/lect0406post.txt (accessed
February 10, 2015).
 Papadimitriou, C., and M. Yannakakis. 1988. Optimization,
approximation, and complexity classes. 20th Annual
ACM Symposium on the Theory of Computing Proceedings.
229234.
 Halldorsson, M., and J. Radhakrishnan. 1994. Greed
is good: Approximating independent sets in sparse and
boundeddegree graphs. 30th ACM Symposium on Theory
of Computing Proceedings. 439–448.
 Yannakakis, M. 1994. On the approximation of maximum
satisfiability. 3rd Annual ACMSIAM Symposium on Discrete Algorithms Proceedings.
Orlando,FL,USA. 475–502.
 Azar, Y., L. Epstein, Y. Richter, and G. Woeginger.
2004. Allnorm approximation algorithms. J. Algorithm.
52(2):120–133.
 Awerbuch, B., Y. Azar, E. Grove, M. Kao, P. Krishman,
and J. Vitter. 1995. Load balancing in the Lp norm. IEEE
Symposium on Foundations of Computer Science (FOCS)
Proceedings.
 Adamy, U., T. Erlebach, D.Mitsche, I. Schurr, B. Speckmann,
and E. Welzl. 2005. Offline admission control
for advance reservations in star networks. Approximation
Online Algorithms 3351:211–224.
[+] About this article
Title
HEURISTIC CERTIFICATES VIA APPROXIMATIONS
Journal
Informatics and Applications
2015, Volume 9, Issue 1, pp 1527
Cover Date
20141030
DOI
10.14357/19922264150103
Print ISSN
19922264
Publisher
Institute of Informatics Problems, Russian Academy of Sciences
Additional Links
Key words
heuristics; approximation algorithm; optimal solution; approximation preserving reducibility
Authors
Sh. Dolev and M. KoganSadetsky
Author Affiliations
Department of Computer Science, BenGurion University of the Negev, BeerSheva 84105, Israel
