کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9657922 | 690117 | 2005 | 17 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The approximability of non-Boolean satisfiability problems and restricted integer programming
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: The approximability of non-Boolean satisfiability problems and restricted integer programming The approximability of non-Boolean satisfiability problems and restricted integer programming](/preview/png/9657922.png)
چکیده انگلیسی
We obtain the results through the constraint satisfaction problem over multi-valued domains, for which we develop approximation algorithms and show non-approximability results. Our parallel approximation algorithms are based on linear programming and random rounding; they are better than previously known sequential algorithms. The non-approximability results are based on new recent progress in the fields of probabilistically checkable proofs and multi-prover one-round proof systems.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 332, Issues 1â3, 28 February 2005, Pages 123-139
Journal: Theoretical Computer Science - Volume 332, Issues 1â3, 28 February 2005, Pages 123-139
نویسندگان
Maria Serna, Luca Trevisan, Fatos Xhafa,