Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10332774 | Journal of Computer and System Sciences | 2014 | 10 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
R. Crowston, M. Fellows, G. Gutin, M. Jones, E.J. Kim, F. Rosamond, I.Z. Ruzsa, S. Thomassé, A. Yeo,