ECCC-Report TR01-025https://eccc.weizmann.ac.il/report/2001/025Comments and Revisions published for TR01-025en-usWed, 28 Mar 2001 18:07:07 +0200
Paper TR01-025
| Approximating Minimum Unsatisfiability of Linear Equations |
Piotr Berman,
Marek Karpinski
https://eccc.weizmann.ac.il/report/2001/025We 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.
Wed, 28 Mar 2001 18:07:07 +0200https://eccc.weizmann.ac.il/report/2001/025