{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:05:44Z","timestamp":1761620744149},"reference-count":46,"publisher":"Elsevier BV","issue":"1-2","license":[{"start":{"date-parts":[[2001,6,1]],"date-time":"2001-06-01T00:00:00Z","timestamp":991353600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,25]],"date-time":"2013-07-25T00:00:00Z","timestamp":1374710400000},"content-version":"vor","delay-in-days":4437,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Artificial Intelligence"],"published-print":{"date-parts":[[2001,6]]},"DOI":"10.1016\/s0004-3702(01)00107-2","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T06:13:42Z","timestamp":1027577622000},"page":"91-131","source":"Crossref","is-referenced-by-count":35,"title":["A general scheme for automatic generation of search heuristics from specification dependencies\u2606\u2606Preliminary versions of this paper were presented in [15,16,18]. This work was supported in part by NSF grant IIS-0086529 and by MURI ONR award N00014-00-1-0617."],"prefix":"10.1016","volume":"129","author":[{"given":"Kalev","family":"Kask","sequence":"first","affiliation":[]},{"given":"Rina","family":"Dechter","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0004-3702(01)00107-2_BIB001","series-title":"Proc. AAAI-93, Washington, DC","article-title":"Approximating probabilistic inference in Bayesian belief networks is NP-hard","author":"Dagum","year":"1993"},{"key":"10.1016\/S0004-3702(01)00107-2_BIB002","series-title":"Encyclopedia of Artificial Intelligence","first-page":"276","article-title":"Constraint networks","author":"Dechter","year":"1992"},{"key":"10.1016\/S0004-3702(01)00107-2_BIB003","series-title":"Proc. 12th Conference on Uncertainty in Artificial Intelligence (UAI-96), Portland, OR","first-page":"211","article-title":"Bucket elimination: A unifying framework for probabilistic inference algorithms","author":"Dechter","year":"1996"},{"key":"10.1016\/S0004-3702(01)00107-2_BIB004","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/S0004-3702(99)00059-4","article-title":"Bucket elimination: A unifying framework for reasoning","volume":"113","author":"Dechter","year":"1999","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S0004-3702(01)00107-2_BIB005","doi-asserted-by":"crossref","first-page":"506","DOI":"10.1145\/3828.3830","article-title":"Generalized best-first search strategies the optimality of A\u2217","volume":"32","author":"Dechter","year":"1985","journal-title":"J. ACM"},{"key":"10.1016\/S0004-3702(01)00107-2_BIB006","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0004-3702(87)90002-6","article-title":"Network-based heuristics for constraint satisfaction problems","volume":"34","author":"Dechter","year":"1987","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S0004-3702(01)00107-2_BIB007","series-title":"Proc. 13th Conference on Uncertainty in Artificial Intelligence (UAI-97), Providence, RI","first-page":"132","article-title":"A scheme for approximating probabilistic inference","author":"Dechter","year":"1997"},{"key":"10.1016\/S0004-3702(01)00107-2_BIB008","series-title":"Principles and Practice of Constraint Programming (CP-2000)","year":"2000"},{"issue":"1\u20133","key":"10.1016\/S0004-3702(01)00107-2_BIB009","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/0004-3702(92)90004-H","article-title":"Partial constraint satisfaction","volume":"58","author":"Freuder","year":"1992","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S0004-3702(01)00107-2_BIB010","series-title":"Performance measurement analysis of search algorithms","author":"Gaschnig","year":"1979"},{"key":"10.1016\/S0004-3702(01)00107-2_BIB011","series-title":"Proc. AAAI-93, Washington, DC","first-page":"28","article-title":"Towards an understanding of hill-climbing procedures for SAT","author":"Gent","year":"1993"},{"key":"10.1016\/S0004-3702(01)00107-2_BIB012","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1007\/s101070050067","article-title":"Lifted flow covers for mixed 0\u20131 integer programs","author":"Gu","year":"1999","journal-title":"Math. Programming"},{"key":"10.1016\/S0004-3702(01)00107-2_BIB013","doi-asserted-by":"crossref","first-page":"1138","DOI":"10.1287\/opre.18.6.1138","article-title":"The travelling salesman problem minimum spanning trees","volume":"18","author":"Held","year":"1970","journal-title":"Oper. Res."},{"key":"10.1016\/S0004-3702(01)00107-2_BIB014","series-title":"Enumerative Approaches to Combinatorial Optimization\u2014Part I","volume":"10","author":"Ibaraki","year":"1987"},{"key":"10.1016\/S0004-3702(01)00107-2_BIB015","series-title":"Proc. IJCAI-99, Stockholm, Sweden","first-page":"426","article-title":"Branch bound with mini-bucket heuristics","author":"Kask","year":"1999"},{"key":"10.1016\/S0004-3702(01)00107-2_BIB016","series-title":"Proc. 15th Conference on Uncertainty in Artificial Intelligence (UAI-99), Stockholm, Sweden","first-page":"314","article-title":"Mini-Bucket heuristics for improved search","author":"Kask","year":"1999"},{"key":"10.1016\/S0004-3702(01)00107-2_BIB017","series-title":"Workshop on AI Statistics (AI-STAT-99)","first-page":"113","article-title":"Stochastic local search for Bayesian networks","author":"Kask","year":"1999"},{"key":"10.1016\/S0004-3702(01)00107-2_BIB018","series-title":"Proc. Conference on Principles and Practice of Constraint Programming (CP-2000)","first-page":"262","article-title":"New search heuristics for Max-CSP","author":"Kask","year":"2000"},{"key":"10.1016\/S0004-3702(01)00107-2_BIB019","series-title":"Proc. IJCAI-95, Montreal, Quebec","first-page":"616","article-title":"GSAT local consistency","author":"Kask","year":"1995"},{"key":"10.1016\/S0004-3702(01)00107-2_BIB020","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/0004-3702(93)90045-D","article-title":"Linear-space best-first search","volume":"62","author":"Korf","year":"1993","journal-title":"Artificial Intelligence"},{"issue":"2","key":"10.1016\/S0004-3702(01)00107-2_BIB021","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1109\/49.661110","article-title":"Iterative decoding of compound codes by probability propagation in graphical models","volume":"16","author":"Kschischang","year":"1998","journal-title":"IEEE J. Selected Areas in Communication"},{"key":"10.1016\/S0004-3702(01)00107-2_BIB022","series-title":"Proc. Conference on Principles and Practice of Constraint Programming (CP-1999), Alexandria, VA","first-page":"303","article-title":"Partition-based lower bound for Max-CSP","author":"Larossa","year":"1999"},{"key":"10.1016\/S0004-3702(01)00107-2_BIB023","doi-asserted-by":"crossref","first-page":"699","DOI":"10.1287\/opre.14.4.699","article-title":"Branch-and-bound methods: A survey","volume":"14","author":"Lawler","year":"1966","journal-title":"Oper. Res."},{"key":"10.1016\/S0004-3702(01)00107-2_BIB024","series-title":"Proc. 10th Conference on Uncertainty in Artificial Intelligence (UAI-93), Amherst, MA","first-page":"342","article-title":"An efficient approach for finding the MPE in belief networks","author":"Li","year":"1993"},{"key":"10.1016\/S0004-3702(01)00107-2_BIB025","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1049\/el:19970362","article-title":"Near shannon limit performance of low density parity check codes","volume":"33","author":"MacKay","year":"1996","journal-title":"Electronic Letters"},{"key":"10.1016\/S0004-3702(01)00107-2_BIB026","series-title":"Principles and Practice of Constraint Programming (CP-98)","year":"1998"},{"issue":"2","key":"10.1016\/S0004-3702(01)00107-2_BIB027","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1109\/49.661103","article-title":"Turbo decoding as an instance of Pearl's belief propagation algorithm","volume":"16","author":"McEliece","year":"1998","journal-title":"IEEE J. Selected Areas in Communication"},{"key":"10.1016\/S0004-3702(01)00107-2_BIB028","series-title":"Proc. AAAI-90, Boston, MA","first-page":"17","article-title":"Solving large scale constraint satisfaction scheduling problems using heuristic repair methods","author":"Minton","year":"1990"},{"key":"10.1016\/S0004-3702(01)00107-2_BIB029","series-title":"Proc. AAAI-93, Washington, DC","first-page":"40","article-title":"The breakout method for escaping from local minima","author":"Morris","year":"1993"},{"issue":"3","key":"10.1016\/S0004-3702(01)00107-2_BIB030","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/0020-0255(92)90070-O","article-title":"Criticizing solutions to relaxed models yields powerful admissible heuristics","volume":"63","author":"Mayer","year":"1992","journal-title":"Inform. Sci."},{"key":"10.1016\/S0004-3702(01)00107-2_BIB031","series-title":"Heuristics: Intelligent Search Strategies","author":"Pearl","year":"1984"},{"key":"10.1016\/S0004-3702(01)00107-2_BIB032","series-title":"Probabilistic Reasoning in Intelligent Systems","author":"Pearl","year":"1988"},{"key":"10.1016\/S0004-3702(01)00107-2_BIB033","doi-asserted-by":"crossref","DOI":"10.1109\/21.31034","article-title":"A connectionist model for diagnostic problem solving","author":"Peng","year":"1989","journal-title":"IEEE Trans. Systems Man Cybernet."},{"key":"10.1016\/S0004-3702(01)00107-2_BIB034","series-title":"Proc. 10th Conference on Uncertainty in Artificial Intelligence","article-title":"Knowledge engineering for large belief networks","author":"Pradhan","year":"1994"},{"key":"10.1016\/S0004-3702(01)00107-2_BIB035","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1007\/BF00993063","article-title":"Machine discovery of effective admissible heuristics","volume":"12","author":"Prieditis","year":"1993","journal-title":"Machine Learning"},{"key":"10.1016\/S0004-3702(01)00107-2_BIB036","series-title":"Proc. Conference on Uncertainty in Artificial Intelligence (UAI-98)","article-title":"Empirical evaluation of approximation algorithms for probabilistic decoding","author":"Rish","year":"1998"},{"key":"10.1016\/S0004-3702(01)00107-2_BIB037","series-title":"Proc. 7th Conference on Uncertainty in Artificial Intelligence (UAI-91), Los Angeles, CA","first-page":"339","article-title":"On the generation of alternative explanations with implications for belief revision","author":"Santos","year":"1991"},{"key":"10.1016\/S0004-3702(01)00107-2_BIB038","series-title":"Proc. AAAI-93, Washington, DC","first-page":"46","article-title":"An empirical study of greedy local search for satisfiability testing","author":"Selman","year":"1993"},{"key":"10.1016\/S0004-3702(01)00107-2_BIB039","series-title":"Proc. AAAI-94, Seattle, WA","first-page":"337","article-title":"Noise strategies for local search","author":"Selman","year":"1994"},{"key":"10.1016\/S0004-3702(01)00107-2_BIB040","series-title":"Proc. AAAI-92, San Jose, CA","first-page":"440","article-title":"A new method for solving hard satisfiability problems","author":"Selman","year":"1992"},{"key":"10.1016\/S0004-3702(01)00107-2_BIB041","series-title":"Uncertainty in Artificial Intelligence, Vol. 4","first-page":"169","article-title":"Axioms for probability and belief-function propagation","author":"Shenoy","year":"1990"},{"key":"10.1016\/S0004-3702(01)00107-2_BIB042","series-title":"Uncertainty in Artificial Intelligence, Vol. 6","first-page":"185","article-title":"A new algorithm for finding map assignments to belief networks","author":"Shimony","year":"1991"},{"key":"10.1016\/S0004-3702(01)00107-2_BIB043","series-title":"Proc. AAAI-92, San Jose, CA","first-page":"570","article-title":"Reasoning MPE to multiply connected belief networks using message-passing","author":"Sy","year":"1992"},{"key":"10.1016\/S0004-3702(01)00107-2_BIB044","series-title":"Proc. AAAI-96, Portland, OR","first-page":"181","article-title":"Russian doll search","author":"Verfaillie","year":"1996"},{"key":"10.1016\/S0004-3702(01)00107-2_BIB045","series-title":"Proc. Conference on Principles and Practice of Constraint Programming (CP-1996), Cambridge, MA","first-page":"482","article-title":"Analysis of heuristic methods for partial constraint satisfaction problems","author":"Wallace","year":"1996"},{"key":"10.1016\/S0004-3702(01)00107-2_BIB046","series-title":"Integer Programming","author":"Wolsey","year":"1998"}],"container-title":["Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0004370201001072?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0004370201001072?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T02:27:20Z","timestamp":1556850440000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0004370201001072"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,6]]},"references-count":46,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2001,6]]}},"alternative-id":["S0004370201001072"],"URL":"https:\/\/doi.org\/10.1016\/s0004-3702(01)00107-2","relation":{},"ISSN":["0004-3702"],"issn-type":[{"value":"0004-3702","type":"print"}],"subject":[],"published":{"date-parts":[[2001,6]]}}}