In this paper we consider a new optimization problem, called MAX HAMMINGDISTANCE(ℱ) where ℱ is a family of Boolean constraints. This problem consists in finding two satisfying assignments that differ in the maximum number of variable values: in other words, the problem looks for the maximum difference between two models of the constraints given in input. We give a complete classification of the approximability properties of MAX HAMMINGDISTANCE(ℱ) by using a specialization of the criteria introduced by Schaefer in order to classify constraint satisfaction problems and subsequently used by Khanna, Sudan, Trevisan, and Williamson to classify constraint satisfaction optimization problems.
ON THE HAMMING DISTANCE OF CONSTRAINT SATISFACTION PROBLEMS / P. CRESCENZI; G. ROSSI. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 288:(2002), pp. 85-100. [10.1016/S0304-3975(01)00146-3]
ON THE HAMMING DISTANCE OF CONSTRAINT SATISFACTION PROBLEMS
CRESCENZI, PIERLUIGI;
2002
Abstract
In this paper we consider a new optimization problem, called MAX HAMMINGDISTANCE(ℱ) where ℱ is a family of Boolean constraints. This problem consists in finding two satisfying assignments that differ in the maximum number of variable values: in other words, the problem looks for the maximum difference between two models of the constraints given in input. We give a complete classification of the approximability properties of MAX HAMMINGDISTANCE(ℱ) by using a specialization of the criteria introduced by Schaefer in order to classify constraint satisfaction problems and subsequently used by Khanna, Sudan, Trevisan, and Williamson to classify constraint satisfaction optimization problems.
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
