Simultaneously Satisfying Linear Equations Over F_2: MaxLin2 and Max-r-Lin2 Parameterized Above Average

Robert Crowston, Michael Fellows, Gregory Gutin, Mark Jones, Frances Rosamond, StéPhan Thomassé & Anders Yeo
In the parameterized problem MaxLin2-AA[$k$], we are given a system with variables x_1,...,x_n consisting of equations of the form Product_{i in I}x_i = b, where x_i,b in {-1, 1} and I is a nonempty subset of {1,...,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...