It is known that large fragments of the class of dense
Minimum Constraint Satisfaction (MIN-CSP) problems do not have
polynomial time approximation schemes (PTASs) contrary to their
Maximum Constraint Satisfaction analogs. In this paper we prove,
somewhat surprisingly, that the minimum satisfaction of dense
instances of kSAT-formulas, ...
more >>>
We give a polynomial time approximation scheme (PTAS) for dense
instances of the NEAREST CODEWORD problem.
