
Universität Bonn > Institut für Informatik > Abteilung V  
CSReports 2001  Copyright 2001 Universität Bonn, Institut für Informatik, Abt. V  
85222 April 3, 2001 
Approximating Minimum Unsatisfiability of Linear Equations
Piotr Berman and Marek Karpinski [Download PostScript] [Download PDF] 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 (MinUnsatisfy 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. 

Last Change:
11/05/14 at 10:22:35
English 
Universität Bonn > Institut für Informatik > Abteilung V 