Abstract: In this paper we investigate methods for selecting the best algorithms in classic distributed constraint optimization problems. While these are NP-complete problems, many heuristics have nonetheless been proposed. We found that the best method to use can change radically based on the specifics of a given problem instance. Thus, dynamic methods are needed that can choose the best approach for a given problem. We found that large differences typically exist in the expected utility between algorithms, allowing for a clear policy. We present a dynamic algorithm selection approach based on this realization. As support for this approach, we describe the results from thousands of trials from Distributed Constraint Optimization problems that demonstrates the strong statistical improvement of this dynamic approach over the static methods they are based on.

Avi Rosenfeld, “Algorithm Selection for Constraint Optimization Domains” International Journal of Advanced Computer Science and Applications(IJACSA), 4(2), 2013. http://dx.doi.org/10.14569/IJACSA.2013.040240

@article{Rosenfeld2013,
title = {Algorithm Selection for Constraint Optimization Domains},
journal = {International Journal of Advanced Computer Science and Applications},
doi = {10.14569/IJACSA.2013.040240},
url = {http://dx.doi.org/10.14569/IJACSA.2013.040240},
year = {2013},
publisher = {The Science and Information Organization},
volume = {4},
number = {2},
author = {Avi Rosenfeld}
}