Polynomial time approximation schemes for dense instances of minimum constraint satisfaction
Bazgan, Cristina; Fernandez de la Vega, Wenceslas; Karpinski, Marek (2003), Polynomial time approximation schemes for dense instances of minimum constraint satisfaction, Random Structures and Algorithms, 23, 1, p. 73-91. 10.1002/rsa.10072
TypeArticle accepté pour publication ou publié
Journal nameRandom Structures and Algorithms
MetadataShow full item record
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Fernandez de la Vega, Wenceslas
Universität Bonn = University of Bonn
Abstract (EN)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 development of a new density sampling technique for k-uniform hypergraphs which could be of independent interest.
Subjects / KeywordsApproximation Algorithms; Approximation Ratios; Polynomial Time Approximation Schemes; Minimum Constraint Satisfaction; Nearest Codeword Problem; Dense Instances; Hypergraph Sampling
Showing items related by title and author.
Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2010) Article accepté pour publication ou publié