The complexity of making unique choices: approximating 1-in-\(k\) SAT. (English) Zbl 1142.68611
Chekuri, Chandra (ed.) et al., Approximation, randomization and combinatorial optimization. Algorithms and techniques. 8th international workshop on approximation algorithms for combinatorial optimization problems, APPROX 2005, and 9th international workshop on randomization and computation, RANDOM 2005, Berkeley, CA, USA, August 22–24, 2005. Proceedings. Berlin: Springer (ISBN 3-540-28239-4/pbk). Lecture Notes in Computer Science 3624, 99-110 (2005).
Summary: We study the approximability of 1-in-\(k\)SAT , the variant of Max \(k\)SAT where a clause is deemed satisfied when precisely one of its literals is satisfied. We also investigate different special cases of the problem, including those obtained by restricting the literals to be unnegated and/or all clauses to have size exactly \(k\). Our results show that the 1-in-\(k\)SAT problem exhibits some rather peculiar phenomena in the realm of constraint satisfaction problems. Specifically, the problem becomes substantially easier to approximate with perfect completeness as well as when negations of literals are not allowed.
For the entire collection see [Zbl 1087.90002].
For the entire collection see [Zbl 1087.90002].
MSC:
| 68W25 | Approximation algorithms |
| 68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |
