کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6874646 | 1441186 | 2018 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Towards a characterization of constant-factor approximable finite-valued CSPs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We study the approximability of (Finite-)Valued Constraint Satisfaction Problems (VCSPs) with a fixed finite constraint language Î consisting of finitary functions on a fixed finite domain. Ene et al. have shown that, under a mild technical condition, the basic LP relaxation is optimal for constant-factor approximation for VCSP(Î) unless the Unique Games Conjecture fails. Using the algebraic approach to the CSP, we give new natural algebraic conditions for the finiteness of the integrality gap for the basic LP relaxation of VCSP(Î) and show how this leads to efficient constant-factor approximation algorithms for several examples that cover all previously known cases that are NP-hard to solve to optimality but admit constant-factor approximation. Finally, we show that the absence of another algebraic condition leads to NP-hardness of constant-factor approximation. Thus, our results indicate where the boundary of constant-factor approximability for VCSPs lies.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 97, November 2018, Pages 14-27
Journal: Journal of Computer and System Sciences - Volume 97, November 2018, Pages 14-27
نویسندگان
VÃctor Dalmau, Andrei Krokhin, Rajsekar Manokaran,