کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9657684 | 690550 | 2005 | 20 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Locally consistent constraint satisfaction problems
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Locally consistent constraint satisfaction problems Locally consistent constraint satisfaction problems](/preview/png/9657684.png)
چکیده انگلیسی
An instance of a constraint satisfaction problem is l-consistent if any l constraints of it can be simultaneously satisfied. For a set Î of constraint types, Ïl(Î ) denotes the largest ratio of constraints which can be satisfied in any l-consistent instance composed by constraints of types from Î . In the case of sets Î consisting of finitely many Boolean predicates, we express the limit Ïâ(Î ):=limlââÏl(Î ) as the minimum of a certain functional on a convex set of polynomials. Our results yield a robust deterministic algorithm (for a fixed set Î ) running in time linear in the size of the input and 1/ε which finds either an inconsistent set of constraints (of size bounded by the function of ε) or a truth assignment which satisfies the fraction of at least Ïâ(Î )-ε of the given constraints. We also compute the values of Ïl({P}) for several specific predicates P.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 348, Issues 2â3, 8 December 2005, Pages 187-206
Journal: Theoretical Computer Science - Volume 348, Issues 2â3, 8 December 2005, Pages 187-206
نویسندگان
ZdenÄk DvoÅák, Daniel Král', OndÅej Pangrác,