__
TR01-034 | 30th April 2001 00:00
__

#### Polynomial Time Approximation Schemes for Dense Instances of Minimum Constraint Satisfaction

TR01-034
Authors:

Cristina Bazgan,

Wenceslas Fernandez de la Vega,

Marek Karpinski
Publication: 30th April 2001 16:29

Downloads: 1403

Keywords:

Approximation Algorithms,

Approximation Ratios,

Dense Instances,

Hypergrah Sampling,

Linear Equations,

lower bounds,

MIN-Ek-LIN2,

MIN-kSAT,

Minimum Constraint Satisfaction,

nearest codeword problem,

Polynomial Time Approximation Schemes
**Abstract:**
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, and linear equations mod 2, Ek-LIN2,

do have PTASs for any k. The MIN-Ek-LIN2 problems are equivalent

to the k-ary versions of the Nearest Codeword problem, the problem

which is known to be exceedingly hard to approximate on general

instances. The method of solution of the above problems depends on

the developement of a new density sampling technique for k-uniform

hypergraphs which could be of independent interest.