ECCC-Report TR01-034https://eccc.weizmann.ac.il/report/2001/034Comments and Revisions published for TR01-034en-usMon, 30 Apr 2001 16:29:56 +0300
Paper TR01-034
| Polynomial Time Approximation Schemes for Dense Instances of Minimum Constraint Satisfaction |
Cristina Bazgan,
Wenceslas Fernandez de la Vega,
Marek Karpinski
https://eccc.weizmann.ac.il/report/2001/034 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.
Mon, 30 Apr 2001 16:29:56 +0300https://eccc.weizmann.ac.il/report/2001/034