TR01-025 Authors: Piotr Berman, Marek Karpinski

Publication: 28th March 2001 18:07

Downloads: 1375

Keywords:

We consider the following optimization problem:

given a system of m linear equations in n variables over a certain field,

a feasible solution is any assignment of values to the variables, and the

minimized objective function is the number of equations that are not

satisfied. For the case of the finite field GF[2], this problem is also

known as the Nearest Codeword problem. In this note we show that for any

constant c there exists a randomized polynomial time algorithm that

approximates the above problem, called the Minimum Unsatisfiability of

Linear Equations (MIN-UNSATISFY for short), with n/(c log n) approximation

ratio. Our results hold for any field in which systems of linear equations

can be solved in polynomial time.