Informatics and Applications
2015, Volume 9, Issue 1, pp 15-27
HEURISTIC CERTIFICATES VIA APPROXIMATIONS
- Sh. Dolev
- M. Kogan-Sadetsky
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 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.
[+] References (15)
- Holland, J. 1971. Genetic algorithms and the optimal
allocation of trials. SIAM J. Comput. 2:88-105.
- Wall, M., and MIT. 1994-2005. 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. 161-166.
- 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. IX-97-7:17-35.
- 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.
1-10.
- http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/cla
ss/15451-s00/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.
229-234.
- Halldorsson, M., and J. Radhakrishnan. 1994. Greed
is good: Approximating independent sets in sparse and
bounded-degree graphs. 30th ACM Symposium on Theory
of Computing Proceedings. 439–448.
- Yannakakis, M. 1994. On the approximation of maximum
satisfiability. 3rd Annual ACM-SIAM Symposium on Discrete Algorithms Proceedings.
Orlando,FL,USA. 475–502.
- Azar, Y., L. Epstein, Y. Richter, and G. Woeginger.
2004. All-norm 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. Off-line 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 15-27
Cover Date
2014-10-30
DOI
10.14357/19922264150103
Print ISSN
1992-2264
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. Kogan-Sadetsky
Author Affiliations
Department of Computer Science, Ben-Gurion University of the Negev, Beer-Sheva 84105, Israel
|