| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427971 | Information Processing Letters | 2008 | 5 Pages |
Abstract
We consider the problem known as MAX-SATISFY: given a system of m linear equations over the rationals, find a maximum set of equations that can be satisfied. Let r be the width of the system, that is, the maximum number of variables in an equation. We give an Ω(m−1+1/r)-approximation algorithm for any fixed r. Previously the best approximation ratio for this problem was Ω((logm)/m) even for r=2. In addition, we slightly improve the hardness results for MAX-SATISFY.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
