TY - GEN

T1 - Approximating minimum unsatisfiability of linear equations

AU - Berman, Piotr

AU - Karpinski, Marek

PY - 2002

Y1 - 2002

N2 - 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/(clogn) approximation ratio. Our results hold for any field in which systems of linear equations can be solved in polynomial time.

AB - 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/(clogn) approximation ratio. Our results hold for any field in which systems of linear equations can be solved in polynomial time.

UR - http://www.scopus.com/inward/record.url?scp=84968835314&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84968835314&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84968835314

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 514

EP - 516

BT - Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002

PB - Association for Computing Machinery

T2 - 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002

Y2 - 6 January 2002 through 8 January 2002

ER -