Charles Darwin University

CDU eSpace
Institutional Repository

 
CDU Staff and Student only
 

Satisfying more than half of a system of linear equations over GF(2): A multivariate approach

Crowston, Robert, Fellows, Michael, Gutin, Gregory, Jones, Mark, Kim, E. J., Rosamond, Frances, Ruzsa, I. Z., Thomsse, S. and Yeo, A. (2014). Satisfying more than half of a system of linear equations over GF(2): A multivariate approach. Journal of Computer and System Sciences,80(4):687-696.

Document type: Journal Article
Citation counts:
Google Scholar Search Google Scholar

IRMA ID 82794376xPUB162
Title Satisfying more than half of a system of linear equations over GF(2): A multivariate approach
Author Crowston, Robert
Fellows, Michael
Gutin, Gregory
Jones, Mark
Kim, E. J.
Rosamond, Frances
Ruzsa, I. Z.
Thomsse, S.
Yeo, A.
Journal Name Journal of Computer and System Sciences
Publication Date 2014
Volume Number 80
Issue Number 4
ISSN 0022-0000   (check CDU catalogue  open catalogue search in new window)
Scopus ID 2-s2.0-84886983523
Start Page 687
End Page 696
Total Pages 10
Place of Publication United States
Publisher Academic Press
HERDC Category C1 - Journal Article (DIISR)
Abstract In the parameterized problem MaxLin2-AA[k ], we are given a system with variables x1,…,xnx1,…,xn consisting of equations of the form ∏i∈Ixi=b∏i∈Ixi=b, where xi,b∈{−1,1}xi,b∈{−1,1} and I⊆[n]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+kW/2+k, where W is the total weight of all equations and k is the parameter (it is always possible for k=0k=0). We show that MaxLin2-AA[k ] has a kernel with at most View the MathML sourceO(k2logk) variables and can be solved in time 2O(klogk)(nm)O(1)2O(klogk)(nm)O(1). This solves an open problem of Mahajan et al. (2006). The problem Max-r-Lin2-AA[k,rk,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,rk,r] has a kernel with at most (2k−1)r(2k−1)r variables.
Keywords MaxLin
Kernel
Fixed-parameter tractable
DOI http://dx.doi.org/10.1016/j.jcss.2013.10.002   (check subscription with CDU E-Gateway service for CDU Staff and Students  check subscription with CDU E-Gateway in new window)
 
Versions
Version Filter Type
Access Statistics: 16 Abstract Views  -  Detailed Statistics
Created: Thu, 07 Aug 2014, 17:09:21 CST