کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10332774 | 687777 | 2014 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Satisfying more than half of a system of linear equations over GF(2): A multivariate approach
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
In the parameterized problem MaxLin2-AA[k], we are given a system with variables x1,â¦,xn consisting of equations of the form âiâIxi=b, where xi,bâ{â1,1} and Iâ[n], each equation has a positive integral weight, and we are to decide whether it is possible to simultaneously satisfy equations of total weight at least W/2+k, where W is the total weight of all equations and k is the parameter (it is always possible for k=0). We show that MaxLin2-AA[k] has a kernel with at most O(k2logk) variables and can be solved in time 2O(klogk)(nm)O(1). This solves an open problem of Mahajan et al. (2006). The problem Max-r-Lin2-AA[k,r] is the same as MaxLin2-AA[k] with two differences: each equation has at most r variables and r is the second parameter. We prove that Max-r-Lin2-AA[k,r] has a kernel with at most (2kâ1)r variables.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 80, Issue 4, June 2014, Pages 687-696
Journal: Journal of Computer and System Sciences - Volume 80, Issue 4, June 2014, Pages 687-696
نویسندگان
R. Crowston, M. Fellows, G. Gutin, M. Jones, E.J. Kim, F. Rosamond, I.Z. Ruzsa, S. Thomassé, A. Yeo,