Abstract
In this work we introduce and study the question of combining multiple heuristics. Given a problem instance, each of the multiple heuristics is capable of computing the correct solution, but has a different cost. In our models the user executes multiple heuristics until one of them terminates with a solution. Given a set of problem instances, we show how to efficiently compute an optimal fixed schedule for a constant number of heuristics, and show that in general, the problem is computationally hard even to approximate (to within a constant factor). We also discuss a probabilistic configuration, in which the problem instances are drawn from some unknown fixed distribution, and show how to compute a near optimal schedule for this setup.
This research was supported on part by an IBM faculty award.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Anthony, M., Bartlett, P.L.: Neural network learning: Theoretical foundations. Cambridge University Press, Cambridge (1999)
Aronov, B., Matousek, J., Sharir, M.: On the sum of squares of cell complexities in hyperplane arrangements. In: SCG 1991: Proceedings of the seventh annual symposium on Computational geometry, pp. 307–313. ACM Press, New York (1991), doi:10.1145/109648.109682
Cesa-Bianchi, N., Freund, Y., Helmbold, D.P., Haussler, D., Schapire, R.E., Warmuth, M.K.: How to use expert advice. Journal of the ACM 44(3), 427–485 (1997)
de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, P.: Computational geometry algorithms and applications, ch. 8, 2nd revised edn., pp. 172–180. Springer, Heidelberg (2000)
Edelsbrunner, H.: Algorithms in combinatorial geometry. Springer, New York (1987)
Giunchiglia, E., Maratea, M., Tacchella, A., Zambonin, D.: Evaluating search heuristics and optimization techniques in propositional satisfiability. In: Goré, R.P., Leitsch, A., Nipkow, T. (eds.) IJCAR 2001. LNCS (LNAI), vol. 2083, Springer, Heidelberg (2001)
Halperin, D.: Arrangements. In: Goodman, J.E., O’Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, pp. 529–562. CRC Press LLC, Boca Raton (2004)
Hochbaum, D.S.: Approximation algorithms for NP-hard problems. PWS Publishing Co., Boston (1997)
Kullmann, O.: Heuristics for SAT algorithms: Searching for some foundations. 23 pages (September 1998), updated September 1999 w.r.t. running times, http://cs-svr1.swan.ac.uk/~csoliver/heur2letter.ps.gz
Li, C.-M., Anbulagan,: Heuristics based on unit propagation for satisfiability problems. In: Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence (IJCAI 1997), Nagoya, Japan, August 23–29 1997, pp. 366–371 (1997)
Pinedo, M.: Scheduling theory, algorithms and systems. Prentice-Hall International Series in Industrial and Systems Engineering. Prentice-Hall, Englewood Cliffs (1995)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sayag, T., Fine, S., Mansour, Y. (2006). Combining Multiple Heuristics. In: Durand, B., Thomas, W. (eds) STACS 2006. STACS 2006. Lecture Notes in Computer Science, vol 3884. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11672142_19
Download citation
DOI: https://doi.org/10.1007/11672142_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-32301-3
Online ISBN: 978-3-540-32288-7
eBook Packages: Computer ScienceComputer Science (R0)