Polynomially decomposable global cost functions in weighted constraint satisfaction
Refereed conference paper presented and published in conference proceedings


全文

其它資訊
摘要In maintaining consistencies, such as GAC*, FDGAC* and weak EDGAC*, for global cost functions, Weighted CSP (WCSP) solvers rely on the projection and extension operations, which entail the computation of the cost functions' minima. Tractability of this minimum computation is essential for efficient execution. Since projections/extensions modify the cost functions, an important issue is tractable projection-safety, concerning whether minimum cost computation remains tractable after projections/extensions. In this paper, we prove that tractable projection-safety is always possible for projections/extensions to/from the millary cost function (W Ø), and always impossible for projections/extensions to/from n-ary cost functions for n ≥ 2. When n = 1, the answer is indefinite. We give a simple negative example, while Lee and Leung's flow-based projection-safe cost functions are also tractable projection-safe. We propose polynomially decomposable cost functions, which are amenable to tractable minimum computation. We further prove that the polynomial decomposability property is unaffected by projections/extensions to/from unary cost functions. Thus, polynomially decomposable cost functions are tractable projection-safe. We show that the SOFT-AMONG, SOFT-REGULAR, SOFT-GRAMMAR and MAX-WEIGHT/MIN-WEIGHT are polynomially decomposable. They are embedded in a WCSP solver for extensive experiments to confirm the feasibility and efficiency of our proposal. Copyright © 2012, Association for the Advancement of Artificial Intelligence. All rights reserved.
著者Lee J.H.M., Leung K.L., Wu Y.
會議名稱26th AAAI Conference on Artificial Intelligence and the 24th Innovative Applications of Artificial Intelligence Conference, AAAI-12 / IAAI-12
會議開始日22.07.2012
會議完結日26.07.2012
會議地點Toronto, ON
會議國家/地區加拿大
出版年份2012
月份11
日期7
卷號1
頁次507 - 513
國際標準書號9781577355687
語言英式英語

上次更新時間 2020-02-09 於 00:30