文章基本信息

标题：Approximating Minimum Unsatisfiability of Linear Equations
本地全文：下载
作者：Piotr Berman ; Marek Karpinski Approximating Minimum
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2001
卷号：2001
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
关键词：Approximation Algorithms , Approximation Ratio , lower bounds , Minimum Unsatisfiability of Linear Equations , Nearest Codeword Problem.