Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-APX-Reports 2001 Copyright 2001 University of Bonn, Department of Computer Science, Abt. V
8968

April 30, 2001

Polynomial Time Approximation Schemes for Dense Instances of Minimum Constraint Satisfaction
Cristina Bazgan, W. Fernandez de la Vega and Marek Karpinski
[Download PostScript] [Download PDF]

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.

Last Change: 11/05/14 at 10:22:08
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V