کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
377331 658404 2009 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Solving connected row convex constraints by variable elimination
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر هوش مصنوعی
پیش نمایش صفحه اول مقاله
Solving connected row convex constraints by variable elimination
چکیده انگلیسی

We propose an algorithm for the class of connected row convex constraints. In this algorithm, we introduce a novel variable elimination method to solve the constraints. This method is simple and able to make use of the sparsity of the problem instances. One of its key operations is the composition of two constraints. We have identified several nice properties of connected row convex constraints. Those properties enable the development of a fast composition algorithm whose complexity is linear to the size of the variable domains. Compared with the existing work including randomized algorithms, the new algorithm has favorable worst case time and working space complexity. Experimental results also show a significant performance margin over the existing consistency based algorithms.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Artificial Intelligence - Volume 173, Issues 12–13, August 2009, Pages 1204-1219