Article

Combining multiple heuristics

Authors:

Tzur Sayag,

Shai Fine,

Yishay MansourAuthors Info & Claims

STACS'06: Proceedings of the 23rd Annual conference on Theoretical Aspects of Computer Science

Pages 242 - 253

https://doi.org/10.1007/11672142_19

Published: 23 February 2006 Publication History

Publisher Site

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.

References

[1]

M. Anthony and Peter L. Bartlett, Neural network learning: Theoretical foundations, Cambridge University Presss, 1999.

Digital Library

Google Scholar

[2]

Boris Aronov, Jiri Matousek, and Micha Sharir, On the sum of squares of cell complexities in hyperplane arrangements, SCG '91: Proceedings of the seventh annual symposium on Computational geometry (New York, NY, USA), ACM Press, 1991, pp. 307-313.

Digital Library

Google Scholar

[3]

Nicolò Cesa-Bianchi, Yoav Freund, David P. Helmbold, David Haussler, Robert E. Schapire, and Manfred K.Warmuth, How to use expert advice, Journal of the ACM 44 (1997), no. 3, 427-485.

Digital Library

Google Scholar

[4]

Mark de Berg, Marc van Kreveld, Mark Overmars, and Ptfried Schwarzkopf, Computational geometry algorithms and applications, second, revised ed., ch. 8, pp. 172- 180, Springer, 2000.

Google Scholar

[5]

Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, USA, 1987.

Digital Library

Google Scholar

[6]

E. Giunchiglia, M. Maratea, A. Tacchella, and D. Zambonin, Evaluating search heuristics and optimization techniques in propositional satisfiability, Proceedings of International Joint Conference on Automated Reasoning (IJCAR'01) (Siena), June 2001, to appear.

Digital Library

Google Scholar

[7]

D. Halperin, Arrangements, Handbook of Discrete and Computational Geometry (Jacob E. Goodman and Joseph O'Rourke, eds.), CRC Press LLC, Boca Raton, FL, 2004, pp. 529-562.

Google Scholar

[8]

Dorit S. Hochbaum (ed.), Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, USA, 1997.

Digital Library

Google Scholar

[9]

O. Kullmann, Heuristics for SAT algorithms: Searching for some foundations, September 1998, 23 pages, updated September 1999 w.r.t. running times, url = http://cs-svr1.swan.ac.uk/ csoliver/heur2letter.ps.gz.

Google Scholar

[10]

Chu-Min Li and Anbulagan, Heuristics based on unit propagation for satisfiability problems, Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence (IJCAI'97) (Nagoya, Japan), August 23-29 1997, pp. 366-371.

Digital Library

Google Scholar

[11]

M. Pinedo, Scheduling theory, algorithms and systems, Prentice-Hall International Series in Industrial and Systems EngineeringPrentice-Hall: Englewood Cliffs, NJ, 1995.

Google Scholar

Cited By

View all

Balcan MDick TSandholm TVitercik E(2024)Learning to Branch: Generalization Guarantees and Limits of Data-Independent DiscretizationJournal of the ACM10.1145/363784071:2(1-73)Online publication date: 10-Apr-2024
https://dl.acm.org/doi/10.1145/3637840
Gagliolo MSchmidhuber J(2010)Algorithm selection as a bandit problem with unbounded lossesProceedings of the 4th international conference on Learning and intelligent optimization10.5555/1893659.1893667(82-96)Online publication date: 18-Jan-2010
https://dl.acm.org/doi/10.5555/1893659.1893667

Combining multiple heuristics
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning

Recommendations

Randomized heuristics for the Capacitated Clustering Problem

In this paper, we investigate the adaptation of the Greedy Randomized Adaptive Search Procedure (GRASP) and Iterated Greedy methodologies to the Capacitated Clustering Problem (CCP). In particular, we focus on the effect of the balance between ...
Optimization of large join queries: combining heuristics and combinatorial techniques

We investigate the use of heuristics in optimizing queries with a large number of joins. Examples of such heuristics are the augmentation and local improvement heuristics described in this paper and a heuristic proposed by Krishnamurthy et al. We also ...
Combining multiple heuristics online
AAAI'07: Proceedings of the 22nd national conference on Artificial intelligence - Volume 2

We present black-box techniques for learning how to interleave the execution of multiple heuristics in order to improve average-case performance. In our model, a user is given a set of heuristics whose only observable behavior is their running time. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STACS'06: Proceedings of the 23rd Annual conference on Theoretical Aspects of Computer Science

February 2006

711 pages

ISBN:3540323015

Editors:
Bruno Durand
LIF, CNRS & Univ. de Provence,, Marseille
,
Wolfgang Thomas
RWTH Aachen University,, Lehrstuhl Informatik 7,, Aachen,, Germany

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 23 February 2006

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Balcan MDick TSandholm TVitercik E(2024)Learning to Branch: Generalization Guarantees and Limits of Data-Independent DiscretizationJournal of the ACM10.1145/363784071:2(1-73)Online publication date: 10-Apr-2024
https://dl.acm.org/doi/10.1145/3637840
Gagliolo MSchmidhuber J(2010)Algorithm selection as a bandit problem with unbounded lossesProceedings of the 4th international conference on Learning and intelligent optimization10.5555/1893659.1893667(82-96)Online publication date: 18-Jan-2010
https://dl.acm.org/doi/10.5555/1893659.1893667

Abstract

References

Cited By

Recommendations

Randomized heuristics for the Capacitated Clustering Problem

Optimization of large join queries: combining heuristics and combinatorial techniques